2018/05/07 by Parter, Merav · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1805.02457
In this paper, we present improved algorithms for the (Δ+1) (vertex) coloring problem in the Congested-Clique model of distributed computing. In this model, the input is a graph on n nodes, initially each node knows only its incident edges, and per round each two nodes can exchange O(log n) bits of information. Our key result is a randomized (Δ+1) vertex coloring algorithm that works in O(loglog Δ⋅ log^* Δ)-rounds. This is achieved by combining the recent breakthrough result of [Chang-Li-Pettie, STOC'18] in the \local model and a degree reduction technique. We also get the following results with high probability: (1) (Δ+1)-coloring for Δ=O((n/log n)1-ε) for any ε∈ (0,1), within O(log(1/ε)log^* Δ) rounds, and (2) (Δ+Δ1/2+o(1))-coloring within O(log^* Δ) rounds. Turning to deterministic algorithms, we show a (Δ+1)-coloring algorithm that works in O(log Δ) rounds.