Improved distributed [Formula: see text] -coloring

We present a randomized distributed algorithm that computes a [Formula: see text] -coloring in any non-complete graph with maximum degree [Formula: see text] in [Formula: see text] rounds, as well as a randomized algorithm that computes a [Formula: see text] -coloring in [Formula: see text] rounds w...

Descripción completa

Detalles Bibliográficos
Autores principales: Ghaffari, Mohsen, Hirvonen, Juho, Kuhn, Fabian, Maus, Yannic
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer Berlin Heidelberg 2021
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8550726/
https://www.ncbi.nlm.nih.gov/pubmed/34720292
http://dx.doi.org/10.1007/s00446-021-00397-4
Descripción
Sumario:We present a randomized distributed algorithm that computes a [Formula: see text] -coloring in any non-complete graph with maximum degree [Formula: see text] in [Formula: see text] rounds, as well as a randomized algorithm that computes a [Formula: see text] -coloring in [Formula: see text] rounds when [Formula: see text] . Both these algorithms improve on an [Formula: see text] -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 [Formula: see text] round lower bound of Brandt et al. (STOC’16).

Ejemplares similares