Dynamic algorithms for graph coloring
Bhattacharya S, Chakrabarty D, Henzinger MH, Nanongkai D. 2018. Dynamic algorithms for graph coloring. 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1–20.
Download (ext.)
https://arxiv.org/abs/1711.04355
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Bhattacharya, Sayan;
Chakrabarty, Deeparnab;
Henzinger, MonikaISTA ;
Nanongkai, Danupon
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].
Publishing Year
Date Published
2018-01-01
Proceedings Title
29th Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher
Society for Industrial and Applied Mathematics
Page
1 - 20
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
New Orleans, LA, United States
Conference Date
2018-01-07 – 2018-01-10
IST-REx-ID
Cite this
Bhattacharya S, Chakrabarty D, Henzinger MH, Nanongkai D. Dynamic algorithms for graph coloring. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2018:1-20. doi:10.1137/1.9781611975031.1
Bhattacharya, S., Chakrabarty, D., Henzinger, M. H., & Nanongkai, D. (2018). Dynamic algorithms for graph coloring. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1–20). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975031.1
Bhattacharya, Sayan, Deeparnab Chakrabarty, Monika H Henzinger, and Danupon Nanongkai. “Dynamic Algorithms for Graph Coloring.” In 29th Annual ACM-SIAM Symposium on Discrete Algorithms, 1–20. Society for Industrial and Applied Mathematics, 2018. https://doi.org/10.1137/1.9781611975031.1.
S. Bhattacharya, D. Chakrabarty, M. H. Henzinger, and D. Nanongkai, “Dynamic algorithms for graph coloring,” in 29th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, United States, 2018, pp. 1–20.
Bhattacharya S, Chakrabarty D, Henzinger MH, Nanongkai D. 2018. Dynamic algorithms for graph coloring. 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1–20.
Bhattacharya, Sayan, et al. “Dynamic Algorithms for Graph Coloring.” 29th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2018, pp. 1–20, doi:10.1137/1.9781611975031.1.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1711.04355