[{"publication_status":"published","citation":{"ieee":"M. H. Henzinger and P. Peng, “Constant-time Dynamic (Δ +1)-Coloring,” <i>ACM Transactions on Algorithms</i>, vol. 18, no. 2. Association for Computing Machinery (ACM), 2022.","apa":"Henzinger, M. H., &#38; Peng, P. (2022). Constant-time Dynamic (Δ +1)-Coloring. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery (ACM). <a href=\"https://doi.org/10.1145/3501403\">https://doi.org/10.1145/3501403</a>","chicago":"Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic (Δ +1)-Coloring.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery (ACM), 2022. <a href=\"https://doi.org/10.1145/3501403\">https://doi.org/10.1145/3501403</a>.","ama":"Henzinger MH, Peng P. Constant-time Dynamic (Δ +1)-Coloring. <i>ACM Transactions on Algorithms</i>. 2022;18(2). doi:<a href=\"https://doi.org/10.1145/3501403\">10.1145/3501403</a>","mla":"Henzinger, Monika H., and Pan Peng. “Constant-Time Dynamic (Δ +1)-Coloring.” <i>ACM Transactions on Algorithms</i>, vol. 18, no. 2, 16, Association for Computing Machinery (ACM), 2022, doi:<a href=\"https://doi.org/10.1145/3501403\">10.1145/3501403</a>.","ista":"Henzinger MH, Peng P. 2022. Constant-time Dynamic (Δ +1)-Coloring. ACM Transactions on Algorithms. 18(2), 16.","short":"M.H. Henzinger, P. Peng, ACM Transactions on Algorithms 18 (2022)."},"abstract":[{"lang":"eng","text":"We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper (Δ +1)-vertex coloring of a graph with maximum degree at most Δ. This improves upon the previous O(log Δ)-time algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning random ranks to vertices and does not need to maintain a hierarchical graph decomposition. We show that our result does not only have optimal running time but is also optimal in the sense that already deciding whether a Δ-coloring exists in a dynamically changing graph with maximum degree at most Δ takes Ω (log n) time per operation."}],"author":[{"first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Peng, Pan","last_name":"Peng","first_name":"Pan"}],"date_updated":"2022-07-27T11:08:13Z","volume":18,"article_processing_charge":"No","_id":"11662","publication_identifier":{"issn":["1549-6325"],"eissn":["1549-6333"]},"extern":"1","user_id":"72615eeb-f1f3-11ec-aa25-d4573ddc34fd","acknowledgement":"We want to thank an anonymous referee who pointed out a mistake in our conference paper as well as suggesting a fix using an approach in References.","oa_version":"None","quality_controlled":"1","year":"2022","doi":"10.1145/3501403","title":"Constant-time Dynamic (Δ +1)-Coloring","article_number":"16","day":"04","type":"journal_article","intvolume":"        18","status":"public","issue":"2","publication":"ACM Transactions on Algorithms","month":"03","article_type":"original","date_published":"2022-03-04T00:00:00Z","publisher":"Association for Computing Machinery (ACM)","scopus_import":"1","language":[{"iso":"eng"}],"date_created":"2022-07-27T10:58:53Z"},{"issue":"4","publication":"ACM Transactions on Algorithms","status":"public","intvolume":"        17","type":"journal_article","day":"04","date_created":"2022-07-27T11:09:06Z","language":[{"iso":"eng"}],"publisher":"Association for Computing Machinery","scopus_import":"1","article_type":"original","date_published":"2021-10-04T00:00:00Z","month":"10","acknowledgement":"The conference version of this article [10] had an error in the analysis of the dynamic matching algorithm. In particular, Lemma 4.5 assumed an independence between adversarial updates to the hierarchy that is in fact true, but which requires a sophisticated proof. We are very grateful to the anonymous reviewers of Transactions on Algorithms for pointing out this mistake in our analysis. The mistake is fixed in Section 4.5. Almost the entire fix is a matter of analysis: the only change to the algorithm itself is the introduction of responsible bits in Algorithm 2. The first author would like to thank Mikkel Thorup and Alan Roytman for a very helpful discussion of the proof of Theorem 1.1.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","quality_controlled":"1","_id":"11663","publication_identifier":{"eissn":["1549-6333"],"issn":["1549-6325"]},"extern":"1","oa":1,"date_updated":"2022-09-09T11:35:44Z","volume":17,"article_processing_charge":"No","arxiv":1,"author":[{"first_name":"Aaron","full_name":"Bernstein, Aaron","last_name":"Bernstein"},{"first_name":"Sebastian","full_name":"Forster, Sebastian","last_name":"Forster"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H"}],"abstract":[{"text":"Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas) and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability.\r\n\r\nIn this article, we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem.\r\n\r\n(1)\r\n\r\nFor dynamic spanner, the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case update time for maintaining a 3-spanner and O(n5/9) for maintaining a 5-spanner. We give a O(1)k log3 (n) high-probability worst-case time bound for maintaining a (2k-1)-spanner, which yields the first worst-case polylog update time for all constant k. (All the results above maintain the optimal tradeoff of stretch 2k-1 and Õ(n1+1/k) edges.)\r\n\r\n(2)\r\n\r\nFor dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O(log 5 (n)) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2+ϵ)-approximate, and hence not maximal.\r\n\r\nOur results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: An algorithm is said to have worst-case expected update time ɑ if for every update σ, the expected time to process σ is at most ɑ. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: A worst-case expected update time of O(1) still allows for the possibility that every 1/f(n) updates requires ϴ (f(n)) time to process, for arbitrarily high f(n). In this article, we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: The query time remains the same, while the update time increases by a factor of O(log 2(n)).\r\n\r\nThus, we achieve our results in two steps:\r\n\r\n(1) First, we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times.\r\n\r\n(2) Then, we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms.","lang":"eng"}],"publication_status":"published","citation":{"mla":"Bernstein, Aaron, et al. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 4, 29, Association for Computing Machinery, 2021, doi:<a href=\"https://doi.org/10.1145/3469833\">10.1145/3469833</a>.","ama":"Bernstein A, Forster S, Henzinger MH. A deamortization approach for dynamic spanner and dynamic maximal matching. <i>ACM Transactions on Algorithms</i>. 2021;17(4). doi:<a href=\"https://doi.org/10.1145/3469833\">10.1145/3469833</a>","ista":"Bernstein A, Forster S, Henzinger MH. 2021. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 17(4), 29.","short":"A. Bernstein, S. Forster, M.H. Henzinger, ACM Transactions on Algorithms 17 (2021).","apa":"Bernstein, A., Forster, S., &#38; Henzinger, M. H. (2021). A deamortization approach for dynamic spanner and dynamic maximal matching. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3469833\">https://doi.org/10.1145/3469833</a>","ieee":"A. Bernstein, S. Forster, and M. H. Henzinger, “A deamortization approach for dynamic spanner and dynamic maximal matching,” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 4. Association for Computing Machinery, 2021.","chicago":"Bernstein, Aaron, Sebastian Forster, and Monika H Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3469833\">https://doi.org/10.1145/3469833</a>."},"article_number":"29","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1810.10932"}],"external_id":{"arxiv":["1810.10932"]},"title":"A deamortization approach for dynamic spanner and dynamic maximal matching","year":"2021","doi":"10.1145/3469833"},{"department":[{"_id":"DaAl"}],"has_accepted_license":"1","date_created":"2021-06-10T19:31:05Z","file":[{"success":1,"creator":"pdavies","file_id":"9542","relation":"main_file","content_type":"application/pdf","checksum":"a21c627683890c309a68f6389302c408","date_created":"2021-06-10T19:33:56Z","file_size":587404,"file_name":"MISMM-arxiv.pdf","access_level":"open_access","date_updated":"2021-06-10T19:33:56Z"}],"date_published":"2021-06-01T00:00:00Z","article_type":"original","month":"06","language":[{"iso":"eng"}],"publisher":"Association for Computing Machinery","file_date_updated":"2021-06-10T19:33:56Z","issue":"2","publication":"ACM Transactions on Algorithms","type":"journal_article","day":"01","status":"public","intvolume":"        17","isi":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1912.05390"}],"article_number":"16","ddc":["000"],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"7802"}]},"ec_funded":1,"year":"2021","doi":"10.1145/3451992","title":"Graph sparsification for derandomizing massively parallel computation with low space","external_id":{"arxiv":["1912.05390"],"isi":["000661311300006"]},"volume":17,"oa":1,"date_updated":"2024-02-28T12:53:09Z","article_processing_charge":"No","arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"Institute of Science and Technology Austria (IST Austria). Email: peter.davies@ist.ac.at. Work partially\r\ndone at the Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP),University of Warwick. Research partially supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 754411, the Centre for Discrete Mathematics and its Applications, a Weizmann-UK Making Connections Grant, and EPSRC award EP/N011163/1.","quality_controlled":"1","oa_version":"Submitted Version","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411"}],"_id":"9541","publication_identifier":{"eissn":["1549-6333"],"issn":["1549-6325"]},"publication_status":"published","citation":{"ista":"Czumaj A, Davies P, Parter M. 2021. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms. 17(2), 16.","short":"A. Czumaj, P. Davies, M. Parter, ACM Transactions on Algorithms 17 (2021).","ama":"Czumaj A, Davies P, Parter M. Graph sparsification for derandomizing massively parallel computation with low space. <i>ACM Transactions on Algorithms</i>. 2021;17(2). doi:<a href=\"https://doi.org/10.1145/3451992\">10.1145/3451992</a>","mla":"Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 2, 16, Association for Computing Machinery, 2021, doi:<a href=\"https://doi.org/10.1145/3451992\">10.1145/3451992</a>.","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3451992\">https://doi.org/10.1145/3451992</a>.","ieee":"A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing massively parallel computation with low space,” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 2. Association for Computing Machinery, 2021.","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2021). Graph sparsification for derandomizing massively parallel computation with low space. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3451992\">https://doi.org/10.1145/3451992</a>"},"author":[{"first_name":"Artur","last_name":"Czumaj","full_name":"Czumaj, Artur"},{"id":"11396234-BB50-11E9-B24C-90FCE5697425","orcid":"0000-0002-5646-9524","last_name":"Davies","full_name":"Davies, Peter","first_name":"Peter"},{"full_name":"Parter, Merav","last_name":"Parter","first_name":"Merav"}],"abstract":[{"text":"The Massively Parallel Computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP’86], we obtain O(log Δ + log log n)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with O(nɛ) space on each machine for any constant ɛ > 0. These algorithms also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel et al. [DISC’17].","lang":"eng"}]},{"status":"public","intvolume":"        14","type":"journal_article","day":"01","publication":"ACM Transactions on Algorithms","issue":"2","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"Association for Computing Machinery","date_published":"2018-04-01T00:00:00Z","article_type":"original","month":"04","date_created":"2022-07-27T11:29:39Z","author":[{"last_name":"Goranci","full_name":"Goranci, Gramoz","first_name":"Gramoz"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"first_name":"Mikkel","last_name":"Thorup","full_name":"Thorup, Mikkel"}],"abstract":[{"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.","lang":"eng"}],"citation":{"short":"G. Goranci, M.H. Henzinger, M. Thorup, ACM Transactions on Algorithms 14 (2018).","ista":"Goranci G, Henzinger MH, Thorup M. 2018. Incremental exact min-cut in polylogarithmic amortized update time. ACM Transactions on Algorithms. 14(2), 17.","ama":"Goranci G, Henzinger MH, Thorup M. Incremental exact min-cut in polylogarithmic amortized update time. <i>ACM Transactions on Algorithms</i>. 2018;14(2). doi:<a href=\"https://doi.org/10.1145/3174803\">10.1145/3174803</a>","mla":"Goranci, Gramoz, et al. “Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.” <i>ACM Transactions on Algorithms</i>, vol. 14, no. 2, 17, Association for Computing Machinery, 2018, doi:<a href=\"https://doi.org/10.1145/3174803\">10.1145/3174803</a>.","chicago":"Goranci, Gramoz, Monika H Henzinger, and Mikkel Thorup. “Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2018. <a href=\"https://doi.org/10.1145/3174803\">https://doi.org/10.1145/3174803</a>.","ieee":"G. Goranci, M. H. Henzinger, and M. Thorup, “Incremental exact min-cut in polylogarithmic amortized update time,” <i>ACM Transactions on Algorithms</i>, vol. 14, no. 2. Association for Computing Machinery, 2018.","apa":"Goranci, G., Henzinger, M. H., &#38; Thorup, M. (2018). Incremental exact min-cut in polylogarithmic amortized update time. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3174803\">https://doi.org/10.1145/3174803</a>"},"publication_status":"published","quality_controlled":"1","oa_version":"Preprint","acknowledgement":"We thank the two anonymous reviewers for their suggestions and comments, which improved the\r\nquality of the article.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["1549-6325"],"eissn":["1549-6333"]},"extern":"1","_id":"11664","article_processing_charge":"No","date_updated":"2022-09-09T11:38:14Z","oa":1,"volume":14,"arxiv":1,"title":"Incremental exact min-cut in polylogarithmic amortized update time","external_id":{"arxiv":["1611.06500"]},"year":"2018","doi":"10.1145/3174803","article_number":"17","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1611.06500"}]},{"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1512.08147"}],"article_number":"51","title":"Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks","external_id":{"arxiv":["1512.08147"]},"doi":"10.1145/3146550","year":"2017","_id":"11665","publication_identifier":{"issn":["1549-6325"],"eissn":["1549-6333"]},"extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"We thank the reviewers of ICALP 2013 for pointing to related articles and to an error in an example\r\ngiven in a previous version of this article. We also thank one of the reviewers of Transactions on\r\nAlgorithms for very detailed comments.","oa_version":"Preprint","quality_controlled":"1","arxiv":1,"date_updated":"2022-09-09T11:57:42Z","volume":13,"oa":1,"article_processing_charge":"No","abstract":[{"lang":"eng","text":"We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We present deterministic (1+ϵ)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network.\r\n\r\nOur technique also leads to a deterministic (1+ϵ)-approximate incremental algorithm for single-source shortest paths in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach (1981), which is optimal under some assumptions (Roditty and Zwick 2011; Henzinger et al. 2015). Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if some approximation is allowed."}],"author":[{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Krinninger","full_name":"Krinninger, Sebastian","first_name":"Sebastian"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"}],"publication_status":"published","citation":{"mla":"Henzinger, Monika H., et al. “Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.” <i>ACM Transactions on Algorithms</i>, vol. 13, no. 4, 51, Association for Computing Machinery, 2017, doi:<a href=\"https://doi.org/10.1145/3146550\">10.1145/3146550</a>.","ama":"Henzinger MH, Krinninger S, Nanongkai D. Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. <i>ACM Transactions on Algorithms</i>. 2017;13(4). doi:<a href=\"https://doi.org/10.1145/3146550\">10.1145/3146550</a>","ista":"Henzinger MH, Krinninger S, Nanongkai D. 2017. Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. ACM Transactions on Algorithms. 13(4), 51.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, ACM Transactions on Algorithms 13 (2017).","apa":"Henzinger, M. H., Krinninger, S., &#38; Nanongkai, D. (2017). Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3146550\">https://doi.org/10.1145/3146550</a>","ieee":"M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks,” <i>ACM Transactions on Algorithms</i>, vol. 13, no. 4. Association for Computing Machinery, 2017.","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2017. <a href=\"https://doi.org/10.1145/3146550\">https://doi.org/10.1145/3146550</a>."},"date_created":"2022-07-27T11:37:23Z","publisher":"Association for Computing Machinery","scopus_import":"1","language":[{"iso":"eng"}],"month":"10","date_published":"2017-10-01T00:00:00Z","article_type":"original","issue":"4","publication":"ACM Transactions on Algorithms","intvolume":"        13","status":"public","day":"01","type":"journal_article"}]