Referenz
Harris, D. G., Schneider, J., & Su, H.-H. (2016). Distributed (\Delta 1)-Coloring in Sublogarithmic Rounds. Paper presented at the Symposium on the Theory of Computing (STOC).
Publikationsart
Beitrag in Konferenztagungsband
Abstract
The (Delta + 1)-coloring problem is a fundamental symmetry breaking problem in distributed computing. We give a new randomized coloring algorithm for (Delta+1)-coloring running in O(sqrt(log Delta))+ 2^O(sqrt( log log n)) rounds with probability 1-1/n in a graph with n nodes and maximum degree Delta. This implies that the (Delta + 1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds by Kuhn, Moscibroda, and Wattenhofer [PODC’04]. Our algorithm also extends to the list-coloring problem where the palette of each node contains Delta + 1 colors.
Mitarbeiter
Einrichtungen
- Institut für Wirtschaftsinformatik
- Hilti Lehrstuhl für Business Process Management