Name
Abstract | ||
|---|---|---|
We present a randomized distributed algorithm that computes a Δ- coloring in any non-complete graph with maximum degree Δ ≥ 4 in O(log Δ) +2O( √ log log n) rounds, as well as a randomized algorithm that computes a Δ-coloring in O((log logn)2) rounds when Δ ε [3,O(1)]. Both these algorithms improve on an O(log3 n/ log Δ)- round algorithm of Panconesi and Srinivasan [STOC'1993], which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Ω(log logn) round lower bound of Brandt et al. [STOC'16].
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3212734.3212764 | PODC '18: ACM Symposium on Principles of Distributed Computing
Egham
United Kingdom
July, 2018 |
Keywords | DocType | ISBN |
distributed computing, distributed graph algorithms, graph coloring | Conference | 978-1-4503-5795-1 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mohsen Ghaffari | 1 | 452 | 44.89 |
| Juho Hirvonen | 2 | 106 | 11.81 |
| Fabian Kuhn | 3 | 4 | 1.77 |
| Yannic Maus | 4 | 25 | 11.43 |