[{"citation":{"chicago":"Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Practical Minimum Cut Algorithms.” ACM Journal of Experimental Algorithmics. Association for Computing Machinery, 2018. https://doi.org/10.1145/3274662.","ista":"Henzinger MH, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. 23, 1–22.","mla":"Henzinger, Monika H., et al. “Practical Minimum Cut Algorithms.” ACM Journal of Experimental Algorithmics, vol. 23, Association for Computing Machinery, 2018, pp. 1–22, doi:10.1145/3274662.","ieee":"M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” ACM Journal of Experimental Algorithmics, vol. 23. Association for Computing Machinery, pp. 1–22, 2018.","short":"M.H. Henzinger, A. Noe, C. Schulz, D. Strash, ACM Journal of Experimental Algorithmics 23 (2018) 1–22.","apa":"Henzinger, M. H., Noe, A., Schulz, C., & Strash, D. (2018). Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. Association for Computing Machinery. https://doi.org/10.1145/3274662","ama":"Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. 2018;23:1-22. doi:10.1145/3274662"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"last_name":"Noe","full_name":"Noe, Alexander","first_name":"Alexander"},{"last_name":"Schulz","full_name":"Schulz, Christian","first_name":"Christian"},{"first_name":"Darren","full_name":"Strash, Darren","last_name":"Strash"}],"external_id":{"arxiv":["1708.06127"]},"article_processing_charge":"No","title":"Practical minimum cut algorithms","quality_controlled":"1","publisher":"Association for Computing Machinery","oa":1,"year":"2018","day":"01","publication":"ACM Journal of Experimental Algorithmics","page":"1-22","doi":"10.1145/3274662","date_published":"2018-10-01T00:00:00Z","date_created":"2022-07-27T08:28:26Z","_id":"11657","article_type":"original","type":"journal_article","status":"public","keyword":["Theoretical Computer Science"],"date_updated":"2022-09-09T11:32:52Z","extern":"1","abstract":[{"lang":"eng","text":"The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi’s contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm runs a factor 7.5× faster on average when using 32 threads. To further speed up computations, we also give a version of our algorithm that performs random edge contractions as preprocessing. This version achieves a lower running time and better parallel scalability at the expense of a higher error rate."}],"oa_version":"Preprint","scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1708.06127","open_access":"1"}],"month":"10","intvolume":" 23","publication_identifier":{"eissn":["1084-6654"],"issn":["1084-6654"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":23},{"article_number":"5","title":"Valuation compressions in VCG-based combinatorial auctions","author":[{"full_name":"Dütting, Paul","last_name":"Dütting","first_name":"Paul"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"full_name":"Starnberger, Martin","last_name":"Starnberger","first_name":"Martin"}],"article_processing_charge":"No","external_id":{"arxiv":["1310.3153"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Dütting P, Henzinger MH, Starnberger M. 2018. Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. 6(2), 5.","chicago":"Dütting, Paul, Monika H Henzinger, and Martin Starnberger. “Valuation Compressions in VCG-Based Combinatorial Auctions.” ACM Transactions on Economics and Computation. Association for Computing Machinery, 2018. https://doi.org/10.1145/3232860.","ama":"Dütting P, Henzinger MH, Starnberger M. Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. 2018;6(2). doi:10.1145/3232860","apa":"Dütting, P., Henzinger, M. H., & Starnberger, M. (2018). Valuation compressions in VCG-based combinatorial auctions. ACM Transactions on Economics and Computation. Association for Computing Machinery. https://doi.org/10.1145/3232860","ieee":"P. Dütting, M. H. Henzinger, and M. Starnberger, “Valuation compressions in VCG-based combinatorial auctions,” ACM Transactions on Economics and Computation, vol. 6, no. 2. Association for Computing Machinery, 2018.","short":"P. Dütting, M.H. Henzinger, M. Starnberger, ACM Transactions on Economics and Computation 6 (2018).","mla":"Dütting, Paul, et al. “Valuation Compressions in VCG-Based Combinatorial Auctions.” ACM Transactions on Economics and Computation, vol. 6, no. 2, 5, Association for Computing Machinery, 2018, doi:10.1145/3232860."},"quality_controlled":"1","publisher":"Association for Computing Machinery","oa":1,"doi":"10.1145/3232860","date_published":"2018-05-01T00:00:00Z","date_created":"2022-07-27T11:46:46Z","day":"01","publication":"ACM Transactions on Economics and Computation","year":"2018","status":"public","keyword":["Theory of computation","Algorithmic game theory and mechanism design","Applied computing","Economics","Simplified mechanisms","Combinatorial auctions with item bidding","Price of anarchy"],"type":"journal_article","article_type":"original","_id":"11667","extern":"1","date_updated":"2022-09-09T12:04:42Z","month":"05","intvolume":" 6","scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1310.3153","open_access":"1"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions, the truthful direct-revelation mechanism that maximizes social welfare is the Vickrey-Clarke-Groves mechanism. For many valuation spaces, computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that increased expressiveness can give rise to additional equilibria of poorer efficiency."}],"volume":6,"issue":"2","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["2167-8383"],"issn":["2167-8375"]},"publication_status":"published"},{"acknowledgement":"We thank the two anonymous reviewers for their suggestions and comments, which improved the\r\nquality of the article.","publisher":"Association for Computing Machinery","quality_controlled":"1","oa":1,"year":"2018","day":"01","publication":"ACM Transactions on Algorithms","doi":"10.1145/3174803","date_published":"2018-04-01T00:00:00Z","date_created":"2022-07-27T11:29:39Z","article_number":"17","citation":{"mla":"Goranci, Gramoz, et al. “Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.” ACM Transactions on Algorithms, vol. 14, no. 2, 17, Association for Computing Machinery, 2018, doi:10.1145/3174803.","short":"G. Goranci, M.H. Henzinger, M. Thorup, ACM Transactions on Algorithms 14 (2018).","ieee":"G. Goranci, M. H. Henzinger, and M. Thorup, “Incremental exact min-cut in polylogarithmic amortized update time,” ACM Transactions on Algorithms, vol. 14, no. 2. Association for Computing Machinery, 2018.","ama":"Goranci G, Henzinger MH, Thorup M. Incremental exact min-cut in polylogarithmic amortized update time. ACM Transactions on Algorithms. 2018;14(2). doi:10.1145/3174803","apa":"Goranci, G., Henzinger, M. H., & Thorup, M. (2018). Incremental exact min-cut in polylogarithmic amortized update time. ACM Transactions on Algorithms. Association for Computing Machinery. https://doi.org/10.1145/3174803","chicago":"Goranci, Gramoz, Monika H Henzinger, and Mikkel Thorup. “Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.” ACM Transactions on Algorithms. Association for Computing Machinery, 2018. https://doi.org/10.1145/3174803.","ista":"Goranci G, Henzinger MH, Thorup M. 2018. Incremental exact min-cut in polylogarithmic amortized update time. ACM Transactions on Algorithms. 14(2), 17."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Goranci, Gramoz","last_name":"Goranci","first_name":"Gramoz"},{"last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"full_name":"Thorup, Mikkel","last_name":"Thorup","first_name":"Mikkel"}],"external_id":{"arxiv":["1611.06500"]},"article_processing_charge":"No","title":"Incremental exact min-cut in polylogarithmic amortized update time","abstract":[{"lang":"eng","text":"We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with O(log3 n log log2 n) amortized time per edge insertion and O(1) query time. This result partially answers an open question posed by Thorup (2007). It also stays in sharp contrast to a polynomial conditional lower bound for the fully dynamic weighted minimum cut problem. Our algorithm is obtained by combining a sparsification technique of Kawarabayashi and Thorup (2015) or its recent improvement by Henzinger, Rao, and Wang (2017), and an exact incremental algorithm of Henzinger (1997).\r\n\r\nWe also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an O(nlog n/ε2) space Monte Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a (1+ε)-approximation to the minimum cut. The algorithm has O((α (n) log3 n)/ε 2) amortized update time and constant query time, where α (n) stands for the inverse of Ackermann function."}],"oa_version":"Preprint","scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1611.06500","open_access":"1"}],"month":"04","intvolume":" 14","publication_identifier":{"eissn":["1549-6333"],"issn":["1549-6325"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":14,"issue":"2","_id":"11664","type":"journal_article","article_type":"original","status":"public","date_updated":"2022-09-09T11:38:14Z","extern":"1"},{"_id":"11757","status":"public","article_type":"original","type":"journal_article","extern":"1","date_updated":"2023-02-10T07:27:39Z","oa_version":"Published Version","abstract":[{"text":"We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an O ( f 2)-approximately optimal solution in O ( f · log(m + n)) amortized update time, where f is the maximum “frequency” of an element, n is the number of sets, and m is the maximum number of elements in the universe at any point in time. (2) For the dynamic b-matching problem, we maintain an O (1)-approximately optimal solution in O (log3 n) amortized update time, where n is the number of nodes in the graph.","lang":"eng"}],"intvolume":" 261","month":"08","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1016/j.ic.2018.02.005"}],"scopus_import":"1","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["0890-5401"]},"issue":"08","volume":261,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Bhattacharya S, Henzinger MH, Italiano G. Dynamic algorithms via the primal-dual method. Information and Computation. 2018;261(08):219-239. doi:10.1016/j.ic.2018.02.005","apa":"Bhattacharya, S., Henzinger, M. H., & Italiano, G. (2018). Dynamic algorithms via the primal-dual method. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2018.02.005","short":"S. Bhattacharya, M.H. Henzinger, G. Italiano, Information and Computation 261 (2018) 219–239.","ieee":"S. Bhattacharya, M. H. Henzinger, and G. Italiano, “Dynamic algorithms via the primal-dual method,” Information and Computation, vol. 261, no. 08. Elsevier, pp. 219–239, 2018.","mla":"Bhattacharya, Sayan, et al. “Dynamic Algorithms via the Primal-Dual Method.” Information and Computation, vol. 261, no. 08, Elsevier, 2018, pp. 219–39, doi:10.1016/j.ic.2018.02.005.","ista":"Bhattacharya S, Henzinger MH, Italiano G. 2018. Dynamic algorithms via the primal-dual method. Information and Computation. 261(08), 219–239.","chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe Italiano. “Dynamic Algorithms via the Primal-Dual Method.” Information and Computation. Elsevier, 2018. https://doi.org/10.1016/j.ic.2018.02.005."},"title":"Dynamic algorithms via the primal-dual method","article_processing_charge":"No","author":[{"first_name":"Sayan","full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Giuseppe","full_name":"Italiano, Giuseppe","last_name":"Italiano"}],"oa":1,"publisher":"Elsevier","quality_controlled":"1","publication":"Information and Computation","day":"01","year":"2018","date_created":"2022-08-08T11:20:03Z","date_published":"2018-08-01T00:00:00Z","doi":"10.1016/j.ic.2018.02.005","page":"219-239"},{"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9783959770811"],"issn":["1868-8969"]},"publication_status":"published","volume":112,"oa_version":"Published Version","abstract":[{"lang":"eng","text":"We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an n^{c}-separator theorem for some c<1. We give a fully dynamic algorithm that maintains (1+epsilon)-approximations of the all-pairs effective resistances of an n-vertex graph G undergoing edge insertions and deletions with O~(sqrt{n}/epsilon^2) worst-case update time and O~(sqrt{n}/epsilon^2) worst-case query time, if G is guaranteed to be sqrt{n}-separable (i.e., it is taken from a class satisfying a sqrt{n}-separator theorem) and its separator can be computed in O~(n) time. Our algorithm is built upon a dynamic algorithm for maintaining approximate Schur complement that approximately preserves pairwise effective resistances among a set of terminals for separable graphs, which might be of independent interest.\r\nWe complement our result by proving that for any two fixed vertices s and t, no incremental or decremental algorithm can maintain the s-t effective resistance for sqrt{n}-separable graphs with worst-case update time O(n^{1/2-delta}) and query time O(n^{1-delta}) for any delta>0, unless the Online Matrix Vector Multiplication (OMv) conjecture is false.\r\nWe further show that for general graphs, no incremental or decremental algorithm can maintain the s-t effective resistance problem with worst-case update time O(n^{1-delta}) and query-time O(n^{2-delta}) for any delta >0, unless the OMv conjecture is false."}],"month":"08","intvolume":" 112","alternative_title":["LIPIcs"],"scopus_import":"1","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2018.40","open_access":"1"}],"extern":"1","date_updated":"2023-02-16T11:08:08Z","_id":"11828","status":"public","type":"conference","conference":{"name":"ESA: Annual European Symposium on Algorithms","location":"Helsinki, Finland","end_date":"2018-08-22","start_date":"2018-08-20"},"day":"14","publication":"26th Annual European Symposium on Algorithms","year":"2018","date_published":"2018-08-14T00:00:00Z","doi":"10.4230/LIPICS.ESA.2018.40","date_created":"2022-08-12T08:26:42Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.” In 26th Annual European Symposium on Algorithms, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ESA.2018.40.","ista":"Goranci G, Henzinger MH, Peng P. 2018. Dynamic effective resistances and approximate schur complement on separable graphs. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 40.","mla":"Goranci, Gramoz, et al. “Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs.” 26th Annual European Symposium on Algorithms, vol. 112, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPICS.ESA.2018.40.","ieee":"G. Goranci, M. H. Henzinger, and P. Peng, “Dynamic effective resistances and approximate schur complement on separable graphs,” in 26th Annual European Symposium on Algorithms, Helsinki, Finland, 2018, vol. 112.","short":"G. Goranci, M.H. Henzinger, P. Peng, in:, 26th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","apa":"Goranci, G., Henzinger, M. H., & Peng, P. (2018). Dynamic effective resistances and approximate schur complement on separable graphs. In 26th Annual European Symposium on Algorithms (Vol. 112). Helsinki, Finland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2018.40","ama":"Goranci G, Henzinger MH, Peng P. Dynamic effective resistances and approximate schur complement on separable graphs. In: 26th Annual European Symposium on Algorithms. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.ESA.2018.40"},"title":"Dynamic effective resistances and approximate schur complement on separable graphs","author":[{"first_name":"Gramoz","last_name":"Goranci","full_name":"Goranci, Gramoz"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"first_name":"Pan","last_name":"Peng","full_name":"Peng, Pan"}],"external_id":{"arxiv":["1802.09111"]},"article_processing_charge":"No","article_number":"40"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Goranci, Gramoz, et al. “A Tree Structure for Dynamic Facility Location.” 26th Annual European Symposium on Algorithms, vol. 112, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPICS.ESA.2018.39.","short":"G. Goranci, M.H. Henzinger, D. Leniowski, in:, 26th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","ieee":"G. Goranci, M. H. Henzinger, and D. Leniowski, “A tree structure for dynamic facility location,” in 26th Annual European Symposium on Algorithms, Helsinki, Finland, 2018, vol. 112.","ama":"Goranci G, Henzinger MH, Leniowski D. A tree structure for dynamic facility location. In: 26th Annual European Symposium on Algorithms. Vol 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPICS.ESA.2018.39","apa":"Goranci, G., Henzinger, M. H., & Leniowski, D. (2018). A tree structure for dynamic facility location. In 26th Annual European Symposium on Algorithms (Vol. 112). Helsinki, Finland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2018.39","chicago":"Goranci, Gramoz , Monika H Henzinger, and Dariusz Leniowski. “A Tree Structure for Dynamic Facility Location.” In 26th Annual European Symposium on Algorithms, Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ESA.2018.39.","ista":"Goranci G, Henzinger MH, Leniowski D. 2018. A tree structure for dynamic facility location. 26th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 112, 39."},"title":"A tree structure for dynamic facility location","external_id":{"arxiv":["1909.06653"]},"article_processing_charge":"No","author":[{"last_name":"Goranci","full_name":"Goranci, Gramoz ","first_name":"Gramoz "},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Dariusz","full_name":"Leniowski, Dariusz","last_name":"Leniowski"}],"article_number":"39","publication":"26th Annual European Symposium on Algorithms","day":"14","year":"2018","date_created":"2022-08-12T08:20:57Z","date_published":"2018-08-14T00:00:00Z","doi":"10.4230/LIPICS.ESA.2018.39","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","extern":"1","date_updated":"2023-02-16T10:50:51Z","_id":"11827","status":"public","conference":{"name":"ESA: Annual European Symposium on Algorithms","end_date":"2018-08-22","location":"Helsinki, Finland","start_date":"2018-08-20"},"type":"conference","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959770811"]},"volume":112,"oa_version":"Published Version","abstract":[{"lang":"eng","text":"We study the metric facility location problem with client insertions and deletions. This setting differs from the classic dynamic facility location problem, where the set of clients remains the same, but the metric space can change over time. We show a deterministic algorithm that maintains a constant factor approximation to the optimal solution in worst-case time O~(2^{O(kappa^2)}) per client insertion or deletion in metric spaces while answering queries about the cost in O(1) time, where kappa denotes the doubling dimension of the metric. For metric spaces with bounded doubling dimension, the update time is polylogarithmic in the parameters of the problem."}],"intvolume":" 112","month":"08","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2018.39","open_access":"1"}],"scopus_import":"1","alternative_title":["LIPIcs"]},{"abstract":[{"text":"In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1+ϵ)-approximation factor, the running time was recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover, we obtain m1+o(1) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary.\r\n\r\nIn contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, ϵ)-hop set introduced by Cohen [12] in the PRAM literature. An (h, ϵ)-hop set of a graph G=(V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+ϵ)-approximated by their h-hop distance (given by a path containing at most h edges) on G′=(V, E ∪ F). Our algorithm can maintain an (no(1), ϵ)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools might be of independent interest.","lang":"eng"}],"oa_version":"Preprint","scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1512.08148","open_access":"1"}],"month":"12","intvolume":" 65","publication_identifier":{"eissn":["1557-735X"],"issn":["0004-5411"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":65,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"11855"}]},"issue":"6","_id":"11768","type":"journal_article","article_type":"original","status":"public","date_updated":"2023-02-21T16:30:41Z","extern":"1","quality_controlled":"1","publisher":"Association for Computing Machinery","oa":1,"year":"2018","day":"01","publication":"Journal of the ACM","page":"1-40","doi":"10.1145/3218657","date_published":"2018-12-01T00:00:00Z","date_created":"2022-08-08T12:33:17Z","citation":{"mla":"Henzinger, Monika H., et al. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” Journal of the ACM, vol. 65, no. 6, Association for Computing Machinery, 2018, pp. 1–40, doi:10.1145/3218657.","apa":"Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2018). Decremental single-source shortest paths on undirected graphs in near-linear total update time. Journal of the ACM. Association for Computing Machinery. https://doi.org/10.1145/3218657","ama":"Henzinger MH, Krinninger S, Nanongkai D. Decremental single-source shortest paths on undirected graphs in near-linear total update time. Journal of the ACM. 2018;65(6):1-40. doi:10.1145/3218657","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, Journal of the ACM 65 (2018) 1–40.","ieee":"M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source shortest paths on undirected graphs in near-linear total update time,” Journal of the ACM, vol. 65, no. 6. Association for Computing Machinery, pp. 1–40, 2018.","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” Journal of the ACM. Association for Computing Machinery, 2018. https://doi.org/10.1145/3218657.","ista":"Henzinger MH, Krinninger S, Nanongkai D. 2018. Decremental single-source shortest paths on undirected graphs in near-linear total update time. Journal of the ACM. 65(6), 1–40."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"}],"external_id":{"arxiv":["1512.08148"]},"article_processing_charge":"No","title":"Decremental single-source shortest paths on undirected graphs in near-linear total update time"},{"publisher":"Society for Industrial and Applied Mathematics","scopus_import":"1","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1711.04355"}],"oa":1,"month":"01","abstract":[{"text":"We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for (Δ + 1)- vertex coloring and (2Δ – 1)-edge coloring in a graph with maximum degree Δ. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results. (1) We present a randomized algorithm which maintains a (Δ + 1)-vertex coloring with O(log Δ) expected amortized update time. (2) We present a deterministic algorithm which maintains a (1 + o(1)Δ-vertex coloring with O(polylog Δ) amortized update time. (3) We present a simple, deterministic algorithm which maintains a (2Δ – 1)-edge coloring with O(log Δ) worst-case update time. This improves the recent O(Δ)-edge coloring algorithm with worst-case update time [4].","lang":"eng"}],"oa_version":"Preprint","page":"1 - 20","doi":"10.1137/1.9781611975031.1","date_published":"2018-01-01T00:00:00Z","date_created":"2022-08-16T12:07:14Z","publication_identifier":{"eisbn":["978-161197503-1"]},"publication_status":"published","year":"2018","day":"01","language":[{"iso":"eng"}],"publication":"29th Annual ACM-SIAM Symposium on Discrete Algorithms","type":"conference","conference":{"name":"SODA: Symposium on Discrete Algorithms","start_date":"2018-01-07","end_date":"2018-01-10","location":"New Orleans, LA, United States"},"status":"public","_id":"11872","author":[{"first_name":"Sayan","last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan"},{"first_name":"Deeparnab","last_name":"Chakrabarty","full_name":"Chakrabarty, Deeparnab"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"last_name":"Nanongkai","full_name":"Nanongkai, Danupon","first_name":"Danupon"}],"external_id":{"arxiv":["1711.04355"]},"article_processing_charge":"No","title":"Dynamic algorithms for graph coloring","date_updated":"2023-02-17T11:39:01Z","citation":{"ista":"Bhattacharya S, Chakrabarty D, Henzinger MH, Nanongkai D. 2018. Dynamic algorithms for graph coloring. 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1–20.","chicago":"Bhattacharya, Sayan, Deeparnab Chakrabarty, Monika H Henzinger, and Danupon Nanongkai. “Dynamic Algorithms for Graph Coloring.” In 29th Annual ACM-SIAM Symposium on Discrete Algorithms, 1–20. Society for Industrial and Applied Mathematics, 2018. https://doi.org/10.1137/1.9781611975031.1.","short":"S. Bhattacharya, D. Chakrabarty, M.H. Henzinger, D. Nanongkai, in:, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2018, pp. 1–20.","ieee":"S. Bhattacharya, D. Chakrabarty, M. H. Henzinger, and D. Nanongkai, “Dynamic algorithms for graph coloring,” in 29th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, United States, 2018, pp. 1–20.","apa":"Bhattacharya, S., Chakrabarty, D., Henzinger, M. H., & Nanongkai, D. (2018). Dynamic algorithms for graph coloring. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1–20). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975031.1","ama":"Bhattacharya S, Chakrabarty D, Henzinger MH, Nanongkai D. Dynamic algorithms for graph coloring. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2018:1-20. doi:10.1137/1.9781611975031.1","mla":"Bhattacharya, Sayan, et al. “Dynamic Algorithms for Graph Coloring.” 29th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2018, pp. 1–20, doi:10.1137/1.9781611975031.1."},"extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"publication_status":"published","year":"2018","publication_identifier":{"eisbn":["978-1-61197-505-5"]},"publication":"20th Workshop on Algorithm Engineering and Experiments","language":[{"iso":"eng"}],"day":"01","page":"48-61","date_created":"2022-08-17T07:04:57Z","doi":"10.1137/1.9781611975055.5","date_published":"2018-01-01T00:00:00Z","abstract":[{"text":"The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi's contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm shows good scalability.","lang":"eng"}],"oa_version":"Preprint","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.06127"}],"scopus_import":"1","quality_controlled":"1","publisher":"Society for Industrial and Applied Mathematics","month":"01","citation":{"ista":"Henzinger MH, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. 20th Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 48–61.","chicago":"Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Practical Minimum Cut Algorithms.” In 20th Workshop on Algorithm Engineering and Experiments, 48–61. Society for Industrial and Applied Mathematics, 2018. https://doi.org/10.1137/1.9781611975055.5.","ama":"Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. In: 20th Workshop on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2018:48-61. doi:10.1137/1.9781611975055.5","apa":"Henzinger, M. H., Noe, A., Schulz, C., & Strash, D. (2018). Practical minimum cut algorithms. In 20th Workshop on Algorithm Engineering and Experiments (pp. 48–61). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975055.5","ieee":"M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” in 20th Workshop on Algorithm Engineering and Experiments, New Orleans, LA, United States, 2018, pp. 48–61.","short":"M.H. Henzinger, A. Noe, C. Schulz, D. Strash, in:, 20th Workshop on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2018, pp. 48–61.","mla":"Henzinger, Monika H., et al. “Practical Minimum Cut Algorithms.” 20th Workshop on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2018, pp. 48–61, doi:10.1137/1.9781611975055.5."},"date_updated":"2023-02-17T14:03:39Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","external_id":{"arxiv":["1708.06127"]},"article_processing_charge":"No","author":[{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger"},{"first_name":"Alexander","full_name":"Noe, Alexander","last_name":"Noe"},{"first_name":"Christian","last_name":"Schulz","full_name":"Schulz, Christian"},{"full_name":"Strash, Darren","last_name":"Strash","first_name":"Darren"}],"title":"Practical minimum cut algorithms","_id":"11882","conference":{"start_date":"2018-01-07","end_date":"2018-01-08","location":"New Orleans, LA, United States","name":"ALENEX: Symposium on Algorithm Engineering and Experiments"},"type":"conference","status":"public"},{"page":"859-887","date_published":"2018-05-01T00:00:00Z","doi":"10.1137/140998925","date_created":"2022-08-17T08:21:23Z","year":"2018","day":"01","publication":"SIAM Journal on Computing","publisher":"Society for Industrial & Applied Mathematics","quality_controlled":"1","oa":1,"author":[{"full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya","first_name":"Sayan"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"full_name":"Italiano, Giuseppe F.","last_name":"Italiano","first_name":"Giuseppe F."}],"external_id":{"arxiv":["1412.1318"]},"article_processing_charge":"No","title":"Deterministic fully dynamic data structures for vertex cover and matching","citation":{"mla":"Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” SIAM Journal on Computing, vol. 47, no. 3, Society for Industrial & Applied Mathematics, 2018, pp. 859–87, doi:10.1137/140998925.","ama":"Bhattacharya S, Henzinger MH, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 2018;47(3):859-887. doi:10.1137/140998925","apa":"Bhattacharya, S., Henzinger, M. H., & Italiano, G. F. (2018). Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/140998925","ieee":"S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” SIAM Journal on Computing, vol. 47, no. 3. Society for Industrial & Applied Mathematics, pp. 859–887, 2018.","short":"S. Bhattacharya, M.H. Henzinger, G.F. Italiano, SIAM Journal on Computing 47 (2018) 859–887.","chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2018. https://doi.org/10.1137/140998925.","ista":"Bhattacharya S, Henzinger MH, Italiano GF. 2018. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 47(3), 859–887."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"id":"11875","status":"public","relation":"earlier_version"}]},"volume":47,"issue":"3","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1412.1318","open_access":"1"}],"month":"05","intvolume":" 47","abstract":[{"lang":"eng","text":"We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph 𝐺=(𝑉,𝐸), with |𝑉|=𝑛 and |𝐸|=𝑚, in 𝑜(𝑚‾‾√) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+𝜖) approximation in 𝑂(log𝑛/𝜖2) amortized time per update. For maximum matching, we show how to maintain a (3+𝜖) approximation in 𝑂(min(𝑛√/𝜖,𝑚1/3/𝜖2) amortized time per update and a (4+𝜖) approximation in 𝑂(𝑚1/3/𝜖2) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457--464]."}],"oa_version":"Preprint","date_updated":"2023-02-21T16:31:30Z","extern":"1","article_type":"original","type":"journal_article","status":"public","_id":"11890"}]