Improved distributed Delta-coloring
2021
We present a randomized distributed algorithm that computes a $$\Delta $$
-coloring in any non-complete graph with maximum degree $$\Delta \ge 4$$
in $$O(\log \Delta ) + 2^{O(\sqrt{\log \log n})}$$
rounds, as well as a randomized algorithm that computes a $$\Delta $$
-coloring in $$O((\log \log n)^2)$$
rounds when $$\Delta \in [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).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
32
References
3
Citations
NaN
KQI