{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:14Z","timestamp":1750220234637,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T00:00:00Z","timestamp":1646352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            We give a fully dynamic (Las-Vegas style) algorithm with\n            <jats:italic>constant expected amortized<\/jats:italic>\n            time per update that maintains a proper (\u0394 +1)-vertex coloring of a graph with maximum degree at most \u0394. This improves upon the previous\n            <jats:italic>O<\/jats:italic>\n            (log \u0394)-time algorithm by Bhattacharya et\u00a0al. (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 \u0394-coloring exists in a dynamically changing graph with maximum degree at most \u0394 takes \u03a9 (log\n            <jats:italic>n<\/jats:italic>\n            ) time per operation.\n          <\/jats:p>","DOI":"10.1145\/3501403","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T11:32:35Z","timestamp":1646393555000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Constant-time Dynamic (\u0394 +1)-Coloring"],"prefix":"10.1145","volume":"18","author":[{"given":"Monika","family":"Henzinger","sequence":"first","affiliation":[{"name":"Faculty of Computer Science, University of Vienna, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pan","family":"Peng","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, University of Science and Technology of China, Hefei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,4]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-319-62127-2_9","volume-title":"Workshop on Algorithms and Data Structures","author":"Barba Luis","year":"2017","unstructured":"Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, Andr\u00e9 van Renssen, Marcel Roeloffzen, and Sander Verdonschot. 2017. Dynamic graph coloring. In Workshop on Algorithms and Data Structures. Springer, 97\u2013108."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2017.05.098"},{"issue":"4","key":"e_1_3_3_4_2","article-title":"Fully dynamic randomized algorithms for graph spanners","volume":"8","author":"Baswana Surender","year":"2012","unstructured":"Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. 2012. Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algor. 8, 4 (2012), 1\u201351.","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00032"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.1"},{"key":"e_1_3_3_7_2","unstructured":"Sayan Bhattacharya Fabrizio Grandoni Janardhan Kulkarni Quanquan C. Liu and Shay Solomon. 2019. Fully dynamic  \\( (\\Delta +1) \\) -coloring in constant update time. Retrieved from https:\/\/arxiv.org\/abs\/1910.02063."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.113"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002168X"},{"key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1145\/2933057.2933083","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing","author":"Censor-Hillel Keren","year":"2016","unstructured":"Keren Censor-Hillel, Elad Haramaty, and Zohar Karnin. 2016. Optimal dynamic distributed MIS. In Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM, 217\u2013226."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00031"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.117"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_3_3_16_2","first-page":"252","volume-title":"Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201983)","author":"Frederickson Greg N.","year":"1983","unstructured":"Greg N. Frederickson. 1983. Data structures for on-line updating of minimum spanning trees (preliminary version). In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201983). 252\u2013257."},{"key":"e_1_3_3_17_2","unstructured":"Monika Henzinger and Alexander Noe. 2021. Random rank-based hierarchical or trivial: Which dynamic graph algorithm performs best in practice? Retrieved from https:\/\/arxiv.org\/abs\/2108.04564."},{"key":"e_1_3_3_18_2","unstructured":"Monika Henzinger and Pan Peng. 2019. Constant-time dynamic ( \\( \\Delta \\) +1)-coloring and weight approximation for minimum spanning forest: Dynamic algorithms meet property testing. Retrieved from http:\/\/arxiv.org\/abs\/1907.04745."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63165-8_214"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_62"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/1076315"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055447"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.92"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"key":"e_1_3_3_29_2","volume-title":"Proceedings of the 26th Annual European Symposium on Algorithms","author":"Solomon Shay","year":"2018","unstructured":"Shay Solomon and Nicole Wein. 2018. Improved dynamic graph coloring. In Proceedings of the 26th Annual European Symposium on Algorithms."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/10.1.85"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055415"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3501403","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3501403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:20Z","timestamp":1750188620000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3501403"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,4]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3501403"],"URL":"https:\/\/doi.org\/10.1145\/3501403","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,3,4]]},"assertion":[{"value":"2020-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}