1 citations · 1 across the 2 of their papers we have counts for
4 papers · 1 filter
Overcoming Congestion in Distributed Coloring
Magnús M. Halldórsson, Alexandre Nolin, Tigran Tonoyan
We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent LOCAL algorithm…
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…
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…
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…