Improved distributed Δ -coloring

Loading...
Thumbnail Image
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Date
2021-08
Major/Subject
Mcode
Degree programme
Language
en
Pages
20
239-258
Series
DISTRIBUTED COMPUTING, Volume 34, issue 4
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).
Description
Funding Information: Partly supported by ERC Grant No. 336495 (ACDC) and Ulla Tuominen Foundation. Publisher Copyright: © 2021, The Author(s).
Keywords
Other note
Citation
Ghaffari, M, Hirvonen, J, Kuhn, F & Maus, Y 2021, ' Improved distributed Δ -coloring ', Distributed Computing, vol. 34, no. 4, pp. 239-258 . https://doi.org/10.1007/s00446-021-00397-4