Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
Authors:
- Yi-Jun ChangYCYi-Jun Chang
- Wenzheng LiWLWenzheng Li
- Seth PettieSPSeth Pettie
- 1 January 2020
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 49 (3) , 497-539
Abstract
Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper, we present a new algorithm for $(\Delta+1)$-list coloring in the randomized ${LOCAL...Keywords
Funding Information
- National Science Foundation (CCF-1514383, CCF-1637546, CCF-1815316)
This publication has 43 references indexed in Scilit:
- Deterministic Distributed Vertex Coloring in Polylogarithmic TimeJournal of the ACM, 2011
- Coloring Graphs with Sparse NeighborhoodsJournal of Combinatorial Theory, Series B, 1999
- Simple distributed Δ+1-coloring of graphsInformation Processing Letters, 1999
- Balls and bins: A study in negative dependenceRandom Structures & Algorithms, 1998
- On the Complexity of Distributed Network DecompositionJournal of Algorithms, 1996
- The local nature of ?-coloring and its algorithmic applicationsCombinatorica, 1995
- Low diameter graph decompositionsCombinatorica, 1993
- Parallel (Δ + 1)-coloring of constant-degree graphsInformation Processing Letters, 1987
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963