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

complexityhypergraphperfect matching

Mathematics Subject Classification ID

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

Related Items (9)

Matching of Given Sizes in Hypergraphs ⋮ Near Perfect Matchings in ${k}$-Uniform Hypergraphs II ⋮ Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees ⋮ Decision problem for perfect matchings in dense 𝑘-uniform 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 ⋮ Unnamed Item ⋮ The complexity of perfect matchings and packings in dense hypergraphs

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

This page was built for publication: COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY