The Complexity of Perfect Matching Problems on Dense Hypergraphs
DOI10.1007/978-3-642-10631-6_64zbMATH Open1273.68180OpenAlexW1603859152WikidataQ57255182 ScholiaQ57255182MaRDI QIDQ3652249FDOQ3652249
Authors: Andrzej Ruciński, Edyta Szymańska, Marek Karpinski 
Publication date: 17 December 2009
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-10631-6_64
Recommendations
- Polynomial-time perfect matchings in dense hypergraphs
- Polynomial-time perfect matchings in dense hypergraphs
- The complexity of perfect matchings and packings in dense hypergraphs
- Computational complexity of the perfect matching problem in hypergraphs with subcritical density
- Finding Perfect Matchings in Dense Hypergraphs
- Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
- On a hypergraph matching problem
- The complexity of almost perfect matchings in uniform hypergraphs with high codegree
- On matchings in hypergraphs
- Perfect matchings in hypergraphs and the Erdős matching conjecture
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (13)
- Polynomial-time perfect matchings in dense hypergraphs
- A geometric theory for hypergraph matching
- Perfect \(f\)-matchings and \(f\)-factors in hypergraphs -- a combinatorial approach
- Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem
- The complexity of perfect matchings and packings in dense hypergraphs
- Polynomial-time perfect matchings in dense hypergraphs
- Computational complexity of the Hamiltonian cycle problem in dense hypergraphs
- Perfect matching in bipartite hypergraphs subject to a demand graph
- The complexity of vertex coloring problems in uniform hypergraphs with high degree
- The complexity of almost perfect matchings in uniform hypergraphs with high codegree
- Computational complexity of the perfect matching problem in hypergraphs with subcritical density
- The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
- Approximating vertex cover in dense hypergraphs
This page was built for publication: The Complexity of Perfect Matching Problems on Dense Hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3652249)
