Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution

DOI10.1137/1.9781611974331.ch140zbMath1410.05221arXiv1507.02674OpenAlexW805422548MaRDI QIDQ4575725

David G. Harris, Aravind Srinivasan

Publication date: 16 July 2018

Published in: ACM Transactions on Algorithms, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.02674

zbMATH Keywords

graph coloringcombinatorial enumerationsatisfiabilityLovász local lemmaLatin transversalsMoser-Tardos algorithmLLL-distributionMT-distributionLLL distributionMT distribution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Transversal (matching) theory (05D15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (4)

Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel ⋮ Unnamed Item ⋮ New bounds for the Moser‐Tardos distribution ⋮ Generalized arboricity of graphs with large girth

This page was built for publication: Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution