Name
Abstract | ||
|---|---|---|
We present a randomized distributed algorithm that computes a Delta-coloring in any non-complete graph with maximum degree Delta >= 4 in O(log Delta)+ 2(O)(root(log log n)) rounds, as well as a randomized algorithm that computes a Delta-coloring in O((log log n)(2)) rounds when Delta is an element of [3, O(1)]. Both these algorithms improve on an O(log(3) n/log Delta)-round algorithm of Panconesi and Srinivasan (STOC'93), which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Omega (log log n) round lower bound of Brandt et al. (STOC'16). |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/s00446-021-00397-4 | DISTRIBUTED COMPUTING |
DocType | Volume | Issue |
Journal | 34 | 4 |
ISSN | Citations | PageRank |
0178-2770 | 0 | 0.34 |
References | Authors | |
0 | 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 |