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

Tölvunarfræðideild

Háskólinn í Reykjavík

Rannsóknarafurð: Kafli í bók/skýrslu/ráðstefnuriti › Ráðstefnuframlag › ritrýni

Útdráttur

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

Upprunalegt tungumál	Enska
Titill gistiútgáfu	34th International Symposium on Distributed Computing (DISC 2020)
DOI	https://doi.org/10.4230/LIPICS.DISC.2020.39
Útgáfustaða	Útgefið - 2020

Aðgangur að skjali

10.4230/LIPICS.DISC.2020.39

Vitna í þetta

@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

Útdráttur

Aðgangur að skjali

Fingerprint

Vitna í þetta