Distributed algorithms for the Lovász local lemma and graph coloring

DOI10.1007/s00446-016-0287-6zbMath1419.68213OpenAlexW2552762966WikidataQ124940867 ScholiaQ124940867MaRDI QIDQ5920074

Hsin-Hao Su, Kai-Min Chung, Seth Pettie

Publication date: 4 September 2017

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-016-0287-6

zbMATH Keywords

coloringlocalityrandomized algorithmsdistributed algorithmsLovász local lemma

Mathematics Subject Classification ID

Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (11)

Locally checkable problems in rooted trees ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Component stability in low-space massively parallel computation ⋮ Distributed coloring of hypergraphs ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Unnamed Item ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ Distributed Lower Bounds for Ruling Sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local computation algorithms for graphs of non-constant degrees
• Asymptotically optimal frugal colouring
• Asymptotic lower bounds for Ramsey functions
• Near-optimal, distributed edge colouring via the nibble method
• Colouring a graph frugally
• Coloring graphs with sparse neighborhoods
• Asymptotically the list colouring constants are 1
• A Note on Vertex List Colouring
• Local Computation
• The Locality of Distributed Symmetry Breaking
• A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)
• An Extension of the Moser--Tardos Algorithmic Local Lemma
• The Randomized Coloring Procedure with Symmetry-Breaking
• A constructive proof of the general lovász local lemma
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• An algorithmic approach to the Lovász local lemma. I
• A parallel algorithmic version of the local lemma
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• An Improved Distributed Algorithm for Maximal Independent Set
• Distributed Graph Coloring: Fundamentals and Recent Developments
• A constructive proof of the Lovász local lemma
• A new technique for distributed symmetry breaking
• On the complexity of distributed graph coloring
• The Moser--Tardos Framework with Partial Resampling
• Fast Distributed Coloring Algorithms for Triangle-Free Graphs
• A lower bound for the distributed Lovász local lemma
• Brief Announcement
• Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovász Local Lemma
• (2Δ — l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
• A constructive algorithm for the Lovász Local Lemma on permutations
• New Constructive Aspects of the Lovász Local Lemma
• Deterministic Algorithms for the Lovász Local Lemma
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
• Moser and tardos meet Lovász
• Graph colouring and the probabilistic method

This page was built for publication: Distributed algorithms for the Lovász local lemma and graph coloring