Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
Abstract
We give a new randomized distributed algorithm for (Δ +1)-coloring in the LOCAL model, running in O (√ log Δ)+ 2 O (√log log n ) rounds in a graph of maximum degree Δ. This implies that the (Δ +1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds of Ω(min(√/log n log log n , /log Δ log log Δ)) by Kuhn, Moscibroda, and Wattenhofer [PODC’04]. Our algorithm also extends to list-coloring where the palette of each node contains Δ +1 colors. We extend the set of distributed symmetry-breaking techniques by performing a decomposition of graphs into dense and sparse parts.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Apr 12, 2018
- Source ID
- 10.1145/3178120
Entities
People
- David G. Harris
- Hsin-hao Su
- Johannes Schneider
Organizations
- Air Force Office of Scientific Research
- National Science Foundation
- University of Liechtenstein
- University of Maryland
- University of North Carolina at Charlotte