Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.19536 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910667347329024 |
|---|---|
| author | Ghaffari, Mohsen Grunau, Christoph |
| author_facet | Ghaffari, Mohsen Grunau, Christoph |
| contents | A recent work by Christiansen, Nowicki, and Rotenberg provides dynamic algorithms for coloring sparse graphs, concretely as a function of the arboricity alpha of the input graph. They give two randomized algorithms: O({alpha} log {alpha}) implicit coloring in poly(log n) worst-case update and query times, and O(min{{alpha} log {alpha}, {alpha} log log log n}) implicit coloring in poly(log n) amortized update and query times (against an oblivious adversary). We improve these results in terms of the number of colors and the time guarantee: First, we present an extremely simple algorithm that computes an O({alpha})-implicit coloring with poly(log n) amortized update and query times. Second, and as the main technical contribution of our work, we show that the time complexity guarantee can be strengthened from amortized to worst-case. That is, we give a dynamic algorithm for implicit O({alpha})-coloring with poly(log n) worst-case update and query times (against an oblivious adversary). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_19536 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dynamic O(arboricity) coloring in polylogarithmic worst-case time Ghaffari, Mohsen Grunau, Christoph Data Structures and Algorithms A recent work by Christiansen, Nowicki, and Rotenberg provides dynamic algorithms for coloring sparse graphs, concretely as a function of the arboricity alpha of the input graph. They give two randomized algorithms: O({alpha} log {alpha}) implicit coloring in poly(log n) worst-case update and query times, and O(min{{alpha} log {alpha}, {alpha} log log log n}) implicit coloring in poly(log n) amortized update and query times (against an oblivious adversary). We improve these results in terms of the number of colors and the time guarantee: First, we present an extremely simple algorithm that computes an O({alpha})-implicit coloring with poly(log n) amortized update and query times. Second, and as the main technical contribution of our work, we show that the time complexity guarantee can be strengthened from amortized to worst-case. That is, we give a dynamic algorithm for implicit O({alpha})-coloring with poly(log n) worst-case update and query times (against an oblivious adversary). |
| title | Dynamic O(arboricity) coloring in polylogarithmic worst-case time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.19536 |