TY - JOUR
T1 - Improved distributed Δ -coloring
AU - Ghaffari, Mohsen
AU - Hirvonen, Juho
AU - Kuhn, Fabian
AU - Maus, Yannic
N1 - Funding Information:
Partly supported by ERC Grant No. 336495 (ACDC) and Ulla Tuominen Foundation.
Publisher Copyright:
© 2021, The Author(s).
PY - 2021/8
Y1 - 2021/8
N2 - We present a randomized distributed algorithm that computes a Δ -coloring in any non-complete graph with maximum degree Δ ≥ 4 in O(logΔ)+2O(loglogn) rounds, as well as a randomized algorithm that computes a Δ -coloring in O((log log n) 2) rounds when Δ ∈ [3 , O(1)]. Both these algorithms improve on an O(log 3n/ log Δ) -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 Ω (log log n) round lower bound of Brandt et al. (STOC’16).
AB - We present a randomized distributed algorithm that computes a Δ -coloring in any non-complete graph with maximum degree Δ ≥ 4 in O(logΔ)+2O(loglogn) rounds, as well as a randomized algorithm that computes a Δ -coloring in O((log log n) 2) rounds when Δ ∈ [3 , O(1)]. Both these algorithms improve on an O(log 3n/ log Δ) -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 Ω (log log n) round lower bound of Brandt et al. (STOC’16).
UR - http://www.scopus.com/inward/record.url?scp=85110386254&partnerID=8YFLogxK
U2 - 10.1007/s00446-021-00397-4
DO - 10.1007/s00446-021-00397-4
M3 - Article
AN - SCOPUS:85110386254
SN - 0178-2770
VL - 34
SP - 239
EP - 258
JO - Distributed Computing
JF - Distributed Computing
IS - 4
ER -