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

DOI10.1142/S0129054110007635zbMATH Open1206.68147MaRDI QIDQ3069732FDOQ3069732

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)

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

zbMATH Keywords

complexityhypergraphperfect matching

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Paths, Trees, and Flowers
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• 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
• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs

Cited In (12)

• The Complexity of Perfect Matching Problems on Dense Hypergraphs
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• The complexity of perfect matchings and packings in dense hypergraphs
• Polynomial-time perfect matchings in dense hypergraphs
• Perfect matching in bipartite hypergraphs subject to a demand graph
• Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
• Decision problem for perfect matchings in dense 𝑘-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
• Matching of Given Sizes in Hypergraphs
• Matchings in 3-uniform hypergraphs of large minimum vertex degree

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)