Computational complexity of the perfect matching problem in hypergraphs with subcritical density

DOI10.1142/S0129054110007635MaRDI QIDQ3069732zbMATH OpenFDO

Authors Andrzej Ruciński, Edyta Szymańska, Marek Karpinski

Publication date 19 January 2011

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054110007635

zbMATH Keywords

complexityhypergraphperfect matching

Mathematics Subject Classification ID

Hypergraphs (05C65) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Complexity of Perfect Matching Problems on Dense Hypergraphs
• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
• The complexity of almost perfect matchings in uniform hypergraphs with high codegree
• The complexity of perfect matchings and packings in dense hypergraphs
• Polynomial-time perfect matchings in dense hypergraphs

Cites work

• A condition for matchability in hypergraphs
• A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• An approximate Dirac-type theorem for k-uniform hypergraphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
• Paths, Trees, and Flowers

Cited in

(15)

• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
• The complexity of perfect matchings and packings in dense hypergraphs
• Matchings in 3-uniform hypergraphs of large minimum vertex degree
• Nearly-perfect hypergraph packing is in NC
• Decision problem for perfect matchings in dense k-uniform hypergraphs
• The complexity of perfect packings in dense graphs
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• The complexity of almost perfect matchings in uniform hypergraphs with high codegree
• The Complexity of Perfect Matching Problems on Dense Hypergraphs
• Polynomial-time perfect matchings in dense hypergraphs
• Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
• Matching of given sizes in hypergraphs
• Perfect matching in bipartite hypergraphs subject to a demand graph
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• On the Keevash-Knox-Mycroft conjecture

This page was built for publication: Computational complexity of the perfect matching problem in hypergraphs with subcritical density

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