Improved distributed Δ -coloring

Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn*, Yannic Maus

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

44 Downloads (Pure)

Abstract

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).

Original languageEnglish
Pages (from-to)239-258
Number of pages20
JournalDISTRIBUTED COMPUTING
Volume34
Issue number4
DOIs
Publication statusPublished - Aug 2021
MoE publication typeA1 Journal article-refereed

Fingerprint

Dive into the research topics of 'Improved distributed Δ -coloring'. Together they form a unique fingerprint.

Cite this