Distributed algorithms for the Lovász local lemma and graph coloring
From MaRDI portal
Publication:5920074
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
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
