Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering

DOI10.1137/19M1249527zbMath1443.68214MaRDI QIDQ5112251

Seth Pettie, Yi-Jun Chang, Wenzheng Li

Publication date: 28 May 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/19m1249527

zbMATH Keywords

graph coloring; distributed algorithm; local model

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

68W15: Distributed algorithms

Related Items

Network Decomposition and Distributed Derandomization (Invited Paper), Superfast coloring in CONGEST via efficient color sampling, Superfast coloring in CONGEST via efficient color sampling, Distributed coloring of hypergraphs, Distributed Symmetry Breaking on Power Graphs via Sparsification

Cites Work

• Parallel \((\Delta +1)\)-coloring of constant-degree graphs
• Low diameter graph decompositions
• A bound on the strong chromatic index of a graph
• Coloring graphs with sparse neighborhoods
• Simple distributed \(\Delta+1\)-coloring of graphs
• The local nature of \(\Delta\)-coloring and its algorithmic applications
• Locality of not-so-weak coloring
• Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks
• Local Computation
• The Locality of Distributed Symmetry Breaking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs
• Distributed Computing: A Locality-Sensitive Approach
• Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
• An Improved Distributed Algorithm for Maximal Independent Set
• An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
• A Time Hierarchy Theorem for the LOCAL Model
• Balls and bins: A study in negative dependence
• On the Complexity of Distributed Network Decomposition
• Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
• Distributed Graph Coloring: Fundamentals and Recent Developments
• (Delta+1) Coloring in the Congested Clique Model
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• An Automatic Speedup Theorem for Distributed Problems
• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
• Faster Deterministic Distributed Coloring Through Recursive List Coloring
• A new technique for distributed symmetry breaking
• On the complexity of distributed graph coloring
• Locally-Iterative Distributed (Δ+ 1)
• An optimal distributed (Δ+1)-coloring algorithm?
• Sublinear Algorithms for (Δ + 1) Vertex Coloring
• Probability Inequalities for Sums of Bounded Random Variables
• A lower bound for the distributed Lovász local lemma
• (2Δ — l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
• Deterministic Distributed Vertex Coloring in Polylogarithmic Time
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
• Concentration of Measure for the Analysis of Randomized Algorithms