Improved distributed Δ -coloring

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

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

4 Sitaatiot (Scopus)
156 Lataukset (Pure)

Abstrakti

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

AlkuperäiskieliEnglanti
Sivut239-258
Sivumäärä20
JulkaisuDistributed Computing
Vuosikerta34
Numero4
DOI - pysyväislinkit
TilaJulkaistu - elok. 2021
OKM-julkaisutyyppiA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Sormenjälki

Sukella tutkimusaiheisiin 'Improved distributed Δ -coloring'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä