3 papers
cs.DC2021
Ultrafast Distributed Coloring of High Degree Graphs
Magnús M. Halldórsson, Alexandre Nolin, Tigran Tonoyan
We give a new randomized distributed algorithm for the -list coloring problem. The algorithm and its analysis dramatically simplify the previous best result known of Chang, Li…
cs.DC2021
Superfast Coloring in CONGEST via Efficient Color Sampling
Magnús M. Halldórsson, Alexandre Nolin
We present a procedure for efficiently sampling colors in the {\congest} model. It allows nodes whose number of colors exceeds their number of neighbors by a constant fraction to s…
cs.DC2020
Coloring Fast Without Learning Your Neighbors' Colors
Magnus M. Halldorsson, Fabian Kuhn, Yannic Maus +1
We give an improved randomized CONGEST algorithm for distance- coloring that uses colors and runs in rounds, improving the recent -rou…