The Complexity of Perfect Matching Problems on Dense Hypergraphs

DOI10.1007/978-3-642-10631-6_64MaRDI QIDQ3652249zbMATH OpenOpenAlexWikidataFDO

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

Mathematics Subject Classification ID

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)

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

Cited in

(13)

• Polynomial-time perfect matchings in dense hypergraphs
• A geometric theory for hypergraph matching
• Perfect matching for regular graphs is AC^ 0-hard for the general matching problem
• Perfect \(f\)-matchings and \(f\)-factors in hypergraphs -- a combinatorial approach
• 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)