The complexity of almost perfect matchings in uniform hypergraphs with high codegree

DOI10.1007/978-3-642-10217-2_43MaRDI QIDQ3651570zbMATH OpenOpenAlexFDO

Authors Edyta Szymańska

Publication date 11 December 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-10217-2_43

zbMATH Keywords

almost perfect matchingspolynomial time algorithm

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
• Computational complexity of the perfect matching problem in hypergraphs with subcritical density
• The Complexity of Perfect Matching Problems on Dense Hypergraphs
• Decision problem for perfect matchings in dense k-uniform hypergraphs
• Polynomial-time perfect matchings in dense hypergraphs

Cited in

(8)

• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
• The complexity of vertex coloring problems in uniform hypergraphs with high degree
• Computational complexity of the perfect matching problem in hypergraphs with subcritical density
• The Complexity of Perfect Matching Problems on Dense Hypergraphs
• Polynomial-time perfect matchings in dense hypergraphs
• A geometric theory for hypergraph matching
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• Matchings in multipartite hypergraphs

This page was built for publication: The complexity of almost perfect matchings in uniform hypergraphs with high codegree

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