Logo image
Back
Distributed graph coloring in a few rounds
Conference proceeding

Distributed graph coloring in a few rounds

Kishore Kothapalli and Sriram Pemmaraju
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, pp.31-40
PODC '11
06/06/2011
DOI: 10.1145/1993806.1993812

View Online

Abstract

This paper considers the question of how many colors a distributed graph coloring algorithm would need to use if it had only k rounds available, for any positive integer k . In our main result, we present an algorithm that runs in O ( k ) rounds for any k bounded below by ©(log log n ) and bounded above by O (√log n ), and uses O ( a Å n 1/ k ) colors to color a graph with arboricity a . This result is optimal since the palette size matches the lower bound of Barenboim and Elkin ( PODC 2008). This result is achieved via the use of several new results developed in this paper on coloring graphs whose edges have been acyclically oriented. For example, suppose that G is an n -vertex, acyclically oriented graph with maximum out-degree Δ o . We present an algorithm that, for any k ≥ 2 loglog n , runs in O ( k ) rounds on G to produce an (i) O (Δ o )-coloring when Δ o Δ ©(max kn 2/ k 2 log 1+1/ k n , 2 k ) and an (ii) O (Δ o Å n 2/ k 2 )-coloring when Δ o ∈ Ω(max k log 1+1/ k n , 2 k ). These results are useful in any setting where it is possible to efficiently compute acyclic orientations of a graph with Δ o << Δ. We derive non-trivial bounds on the palette size even when k < 2 loglog n . Our main technical contributions can be summarized as: (i) developing a k -round version of the algorithm of Kothapalli et al. ( IPDPS 2006 ) which computes an O (?)-coloring of a graph in O (√log n ) rounds, and (ii) developing an oriented version of the Brooks-Vizing coloring result of Grable and Panconesi ( SODA 1998 ).
 distributed algorithms graph coloring oriented graphs symmetry breaking

Details

Metrics

13 Record Views
Logo image