[{"doi":"10.4230/LIPIcs.STACS.2020.53","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."}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.STACS.2020.53"}],"publication_status":"published","publication":"37th International Symposium on Theoretical Aspects of Computer Science","author":[{"full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Peng, Pan","last_name":"Peng","first_name":"Pan"}],"conference":{"location":"Montpellier, France","end_date":"2020-03-13","name":"STACS: Symposium on Theoretical Aspects of Computer Science","start_date":"2020-03-10"},"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","volume":154,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","extern":"1","scopus_import":"1","language":[{"iso":"eng"}],"date_updated":"2024-11-06T11:57:29Z","intvolume":"       154","type":"conference","alternative_title":["LIPIcs"],"date_published":"2020-03-04T00:00:00Z","status":"public","arxiv":1,"external_id":{"arxiv":["1907.04745"]},"year":"2020","title":"Constant-time dynamic (Δ+1)-coloring","oa":1,"citation":{"short":"M. Henzinger, P. Peng, in:, 37th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, vol. 154, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">10.4230/LIPIcs.STACS.2020.53</a>.","ista":"Henzinger M, Peng P. 2020. Constant-time dynamic (Δ+1)-coloring. 37th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 154, 53.","chicago":"Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” In <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">https://doi.org/10.4230/LIPIcs.STACS.2020.53</a>.","apa":"Henzinger, M., &#38; Peng, P. (2020). Constant-time dynamic (Δ+1)-coloring. In <i>37th International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 154). Montpellier, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">https://doi.org/10.4230/LIPIcs.STACS.2020.53</a>","ieee":"M. Henzinger and P. Peng, “Constant-time dynamic (Δ+1)-coloring,” in <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, Montpellier, France, 2020, vol. 154.","ama":"Henzinger M, Peng P. Constant-time dynamic (Δ+1)-coloring. In: <i>37th International Symposium on Theoretical Aspects of Computer Science</i>. Vol 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">10.4230/LIPIcs.STACS.2020.53</a>"},"oa_version":"Published Version","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771405"]},"article_number":"53","month":"03","day":"04","_id":"11825","fulldoi":"https://doi.org/10.4230/LIPIcs.STACS.2020.53","date_created":"2022-08-12T07:53:05Z"}]
