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)

zbMATH Keywords

complexityhypergraphperfect matching

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A condition for matchability in hypergraphs
• A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• 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

(14)

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

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)