Near-optimal distributed degree+1 coloring
Magnús M. Halldórsson, Fabian Kühn, Alexandre Nolin, Tigran Tonoyan
Abstract
We present a new approach to randomized distributed graph coloring that is simpler and more efficient than previous ones. In particular, it allows us to tackle the (deg+1)-list-coloring (D1LC) problem, where each node v of degree dv is assigned a palette of dv+1 colors, and the objective is to find a proper coloring using these palettes. While for (Δ+1)-coloring (where Δ is the maximum degree), there is a fast randomized distributed O(log3logn)-round algorithm due to Chang, Li, and Pettie, no o(logn)-round algorithms are known for the D1LC problem.
Topics & Concepts
Degree (music)Greedy coloringGraph coloringList coloringComputer scienceComplete coloringRandomized algorithmFractional coloringEdge coloringCombinatoricsGraphMathematicsDiscrete mathematicsAlgorithmTheoretical computer scienceGraph powerPhysicsAcousticsLine graphComplexity and Algorithms in GraphsOptimization and Search ProblemsAdvanced Graph Theory Research