Ultrafast Distributed Coloring of High Degree Graphs

05/10/2021
by   Magnus M. Halldorsson, et al.
0

We give a new randomized distributed algorithm for the Δ+1-list coloring problem. The algorithm and its analysis dramatically simplify the previous best result known of Chang, Li, and Pettie [SICOMP 2020]. This allows for numerous refinements, and in particular, we can color all n-node graphs of maximum degree Δ≥log^2+Ω(1) n in O(log^* n) rounds. The algorithm works in the CONGEST model, i.e., it uses only O(log n) bits per message for communication. On low-degree graphs, the algorithm shatters the graph into components of size poly(log n) in O(log^* Δ) rounds, showing that the randomized complexity of Δ+1-list coloring in CONGEST depends inherently on the deterministic complexity of related coloring problems.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset