Finding independent transversals efficiently
From MaRDI portal
Publication:4987260
DOI10.1017/S0963548320000127zbMath1467.05266arXiv1811.02687MaRDI QIDQ4987260
Penny E. Haxell, Alessandra Graf
Publication date: 30 April 2021
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.02687
Extremal problems in graph theory (05C35) Transversal (matching) theory (05D15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)
Related Items (2)
Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel ⋮ Entropy compression versus Lovász local lemma
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extremal problems for transversals in graphs with bounded degree
- The circular chromatic index of graphs of high girth
- Ryser's conjecture for tripartite 3-graphs
- The clique complex and hypergraph matching
- The linear arboricity of graphs
- On complete subgraphs of \(r\)-chromatic graphs
- A note on a conjecture of Ryser
- Almost perfect matchings in random uniform hypergraphs
- Independent transversals in \(r\)-partite graphs
- Bounded size components -- partitions and transversals.
- Partitioning into graphs with only small components
- Triangulated spheres and colored cliques
- A revival of the girth conjecture
- A condition for matchability in hypergraphs
- Finding perfect matchings in bipartite hypergraphs
- Sets of elements that pairwise generate a linear group
- Independent systems of representatives in weighted graphs
- A Note on Vertex List Colouring
- On hitting all maximum cliques with an independent set
- On Forming Committees
- An Improvement of the Lovász Local Lemma via Cluster Expansion
- A Sharper Local Lemma with Improved Applications
- Random Walks That Find Perfect Objects and the Lovász Local Lemma
- Santa claus meets hypergraph matchings
- An Extension of the Moser--Tardos Algorithmic Local Lemma
- Odd Independent Transversals are Odd
- The intersection of a matroid and a simplicial complex
- An improved bound for the strong chromatic number
- Santa Claus Meets Hypergraph Matchings
- A constructive proof of the general lovász local lemma
- An algorithmic approach to the Lovász local lemma. I
- Complete Subgraphs of r-partite Graphs
- Hall's theorem for hypergraphs
- On the Strong Chromatic Number
- Transversals of Vertex Partitions in Graphs
- Lopsidependency in the Moser-Tardos Framework
- A constructive proof of the Lovász local lemma
- Hitting all maximum cliques with a stable set using lopsided independent transversals
- The Moser--Tardos Framework with Partial Resampling
- Edge Colouring with Delays
- A Note on Hitting Maximum and Maximal Cliques With a Stable Set
- A constructive algorithm for the Lovász Local Lemma on permutations
- Deterministic Algorithms for the Lovász Local Lemma
- Moser and tardos meet Lovász
- Algorithms for Weighted Independent Transversals and Strong Colouring
This page was built for publication: Finding independent transversals efficiently
