The Library
Fully dynamic (Δ +1)-coloring in O(1) update time
Tools
Bhattacharya, Sayan, Grandoni, Fabrizio, Kulkarni, Janardhan, Liu, Quanquan C. and Solomon, Shay (2022) Fully dynamic (Δ +1)-coloring in O(1) update time. ACM Transactions on Algorithms , 18 (2). pp. 1-25. 10. doi:10.1145/3494539 ISSN 1549-6325.
|
PDF
WRAP-Fully-Dynamic-1-Coloring-in-O1-Update-Time-2022.pdf - Accepted Version - Requires a PDF viewer. Download (883Kb) | Preview |
|
PDF
dcs-140322-wrap--copyright.pdf - Permissions Correspondence Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (13Kb) |
Official URL: http://dx.doi.org/10.1145/3494539
Abstract
The problem of (Δ +1)-vertex coloring a graph of maximum degree Δ has been extremely well studied over the years in various settings and models. Surprisingly, for the dynamic setting, almost nothing was known until recently. In SODA’18, Bhattacharya, Chakrabarty, Henzinger and Nanongkai devised a randomized algorithm for maintaining a (Δ +1)-coloring with O(log Δ) expected amortized update time. In this article, we present an improved randomized algorithm for (Δ +1)-coloring that achieves O(1) amortized update time and show that this bound holds not only in expectation but also with high probability.
Our starting point is the state-of-the-art randomized algorithm for maintaining a maximal matching (Solomon, FOCS’16). We carefully build on the approach of Solomon, but, due to inherent differences between the maximal matching and (Δ +1)-coloring problems, we need to deviate significantly from it in several crucial and highly nontrivial points.
Item Type: | Journal Article | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Graph coloring, Graph coloring -- Mathematical models, Graph algorithms, Numerical analysis | ||||||||||||||||||
Journal or Publication Title: | ACM Transactions on Algorithms | ||||||||||||||||||
Publisher: | Association for Computing Machinery, Inc. | ||||||||||||||||||
ISSN: | 1549-6325 | ||||||||||||||||||
Official Date: | April 2022 | ||||||||||||||||||
Dates: |
|
||||||||||||||||||
Volume: | 18 | ||||||||||||||||||
Number: | 2 | ||||||||||||||||||
Page Range: | pp. 1-25 | ||||||||||||||||||
Article Number: | 10 | ||||||||||||||||||
DOI: | 10.1145/3494539 | ||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||
Reuse Statement (publisher, data, author rights): | © ACM, 2022. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Algorithms, 18, 2, (2022) http://doi.acm.org/10.1145/3494539. | ||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
Copyright Holders: | Owner/author(s) | ||||||||||||||||||
Date of first compliant deposit: | 21 March 2022 | ||||||||||||||||||
Date of first compliant Open Access: | 22 March 2022 | ||||||||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year