COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY

DOI10.1142/S0129054110007635zbMath1206.68147MaRDI QIDQ3069732

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

Publication date: 19 January 2011

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

zbMATH Keywords

complexity; hypergraph; perfect matching

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C65: Hypergraphs

Related Items

Matching of Given Sizes in Hypergraphs, Polynomial-time perfect matchings in dense hypergraphs, Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs, Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees, The complexity of perfect matchings and packings in dense hypergraphs, Unnamed Item, 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

Cites Work

• Unnamed Item
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
• A condition for matchability in hypergraphs
• On Perfect Matchings in Uniform Hypergraphs with Large Minimum Vertex Degree
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
• Paths, Trees, and Flowers