Nearly optimal distributed edge coloring in O(log log n) rounds

Abstract

An extremely simple distributed randomized algorithm is presented which with high probability properly edge colors a given graph using (1 + ϵ)Δ colors, where Δ is the maximum degree of the graph and ϵ is any given positive constant. The algorithm is very fast. In particular, for graphs with sufficiently large vertex degrees (larger than polylog n, but smaller than any positive power of n), the algorithm requires only O(log log n) communication rounds. The algorithm is inherently distributed, but can be implemented on the PRAM, where it requires O(mΔ) processors and O(log Δ log log n) time, or in a sequential setting, where it requires O(mΔ) time. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 385–405 (1997)