aalto1 untyped-item.component.html
Improved distributed Δ -coloring
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
20
Series
Distributed Computing, Volume 34, issue 4, pp. 239-258
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