Coloring Fast Without Learning Your Neighbors' Colors

Magnús M. Halldórsson; Fabian Kuhn; Yannic Maus; Alexandre Nolin

doi:10.4230/LIPICS.DISC.2020.39

Coloring Fast Without Learning Your Neighbors' Colors

Magnús M. Halldórsson
, Fabian Kuhn
, Yannic Maus
, Alexandre Nolin

Department of Computer Science

Reykjavik University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We give an improved randomized CONGEST algorithm for distance-2 coloring that uses Δ²+1 colors and runs in O(log n) rounds, improving the recent O(log Δ ⋅ log n)-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to O(log Δ) + 2^{O(√{log log n})}.

Original language	English
Title of host publication	34th International Symposium on Distributed Computing (DISC 2020)
DOIs	https://doi.org/10.4230/LIPICS.DISC.2020.39
Publication status	Published - 2020

Access to Document

10.4230/LIPICS.DISC.2020.39

Cite this

@inproceedings{51891efdaeb641a2b216fa35bedc0f36,

title = "Coloring Fast Without Learning Your Neighbors' Colors",

abstract = "We give an improved randomized CONGEST algorithm for distance-2 coloring that uses Δ²+1 colors and runs in O(log n) rounds, improving the recent O(log Δ ⋅ log n)-round algorithm in [Halld{\'o}rsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to O(log Δ) + 2\textasciicircum{}\{O(√\{log log n\})\}.",

author = "Halld{\'o}rsson, \{Magn{\'u}s M.\} and Fabian Kuhn and Yannic Maus and Alexandre Nolin",

year = "2020",

doi = "10.4230/LIPICS.DISC.2020.39",

language = "English",

booktitle = "34th International Symposium on Distributed Computing (DISC 2020)",

}

TY - GEN

T1 - Coloring Fast Without Learning Your Neighbors' Colors

AU - Halldórsson, Magnús M.

AU - Kuhn, Fabian

AU - Maus, Yannic

AU - Nolin, Alexandre

PY - 2020

Y1 - 2020

N2 - We give an improved randomized CONGEST algorithm for distance-2 coloring that uses Δ²+1 colors and runs in O(log n) rounds, improving the recent O(log Δ ⋅ log n)-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to O(log Δ) + 2^{O(√{log log n})}.

AB - We give an improved randomized CONGEST algorithm for distance-2 coloring that uses Δ²+1 colors and runs in O(log n) rounds, improving the recent O(log Δ ⋅ log n)-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to O(log Δ) + 2^{O(√{log log n})}.

UR - https://drops.dagstuhl.de/opus/volltexte/2020/13117/

U2 - 10.4230/LIPICS.DISC.2020.39

DO - 10.4230/LIPICS.DISC.2020.39

M3 - Conference contribution

BT - 34th International Symposium on Distributed Computing (DISC 2020)

ER -

Coloring Fast Without Learning Your Neighbors' Colors

Abstract

Access to Document

Fingerprint

Cite this