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