2018/05/07 by Merav Parter, Parter, Merav · 2 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1805.02457
Appeared in ICALP'18 (the update version adds a missing part in the deterministic coloring procedure)
arxiv created 2020/01/12 · arxiv updated 2020/01/14
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.