The Library
Dynamic algorithms for graph coloring
Tools
Bhattacharya, Sayan, Chakrabarty, Deeparnab, Henzinger, Monika and Nanongkai, Danupon (2018) Dynamic algorithms for graph coloring. In: Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, USA, 7-10 Jan 2018. Published in: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1-20. ISBN 9781611975031. doi:10.1137/1.9781611975031.1
|
PDF
WRAP-dynamic-algorithms-graph-coloring-Bhattacharya-2017.pdf - Accepted Version - Requires a PDF viewer. Download (901Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/1.9781611975031.1
Abstract
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].
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Algorithms, Graph coloring | ||||||||||||
Journal or Publication Title: | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||||||||
Publisher: | Society for Industrial and Applied Mathematics | ||||||||||||
ISBN: | 9781611975031 | ||||||||||||
Book Title: | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||||||||
Official Date: | 2018 | ||||||||||||
Dates: |
|
||||||||||||
Page Range: | pp. 1-20 | ||||||||||||
DOI: | 10.1137/1.9781611975031.1 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 16 January 2018 | ||||||||||||
Date of first compliant Open Access: | 16 January 2018 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms | ||||||||||||
Type of Event: | Conference | ||||||||||||
Location of Event: | New Orleans, USA | ||||||||||||
Date(s) of Event: | 7-10 Jan 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year