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

DOI10.1145/2611462.2611465zbMath1321.68461OpenAlexW2009970369MaRDI QIDQ5892130

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

Publication date: 3 September 2015

Published in: Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2611462.2611465

zbMATH Keywords

probabilistic methodlocalityconstructive algorithmdistributed graph coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (6)

On the Lovász Theta Function for Independent Sets in Sparse Graphs ⋮ What can be sampled locally? ⋮ Unnamed Item ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ Distributed coloring algorithms for triangle-free graphs

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