A note on finding large transversals efficiently

DOI10.1002/JCD.21990MaRDI QIDQ6938924zbMATH OpenFDO

Authors Michael Anastos, Patrick Morris

Publication date 22 August 2025

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/JCD.21990

zbMATH Keywords

deterministic algorithm with polynomial running time

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Transversal (matching) theory (05D15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05)

Cites work

• A constructive proof of the general Lovász local lemma
• A counterexample to Stein's equi-\(n\)-square conjecture
• Algorithmic and enumerative aspects of the Moser-Tardos distribution
• An improvement of the Lovász local lemma via cluster expansion
• Combinatorial matrix theory
• Lopsided Lovász Local lemma and Latin transversals
• New bounds for the Moser-Tardos distribution
• On a conjecture of Stein
• Transversals of latin squares and their generalizations

This page was built for publication: A note on finding large transversals efficiently

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6938924)