Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
From MaRDI portal
Publication:6487489
DOI10.4230/lipics.disc.2017.18zbMath1515.68367MaRDI QIDQ6487489
Mohsen Ghaffari, Manuela Fischer
Publication date: 3 February 2023
Lovász local lemmadistributed graph algorithmsfrugal coloringdefective coloringlocally checkable labeling problemslist vertex-coloring
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)
This page was built for publication: Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy