2010/01/01 by Robin A. Moser, Gábor Tardos · 15 citations
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Complexity and Algorithms in Graphs
paper · doi:10.1145/1667053.1667060
openalex publication_date 2010/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/14
The Lovász Local Lemma discovered by Erdős and Lovász in 1975 is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In 1991, József Beck was the first to demonstrate that a constructive variant can be given under certain more restrictive conditions, starting a whole line of research aimed at improving his algorithm's performance and relaxing its restrictions. In the present article, we improve upon recent findings so as to provide a method for making almost all known applications of the general Local Lemma algorithmic.