Maximum bounded \(H\)-matching is Max SNP-complete
From MaRDI portal
Publication:1321820
DOI10.1016/0020-0190(94)90105-8zbMath0803.68089OpenAlexW2090480826MaRDI QIDQ1321820
Publication date: 3 May 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)90105-8
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (13)
Looking at the stars ⋮ A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ The minimum degree threshold for perfect graph packings ⋮ On ring grooming in optical networks ⋮ Matching and weighted \(P_2\)-packing: algorithms and kernels ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ The Complexity of Perfect Packings in Dense Graphs ⋮ Improved Algorithms for Several Parameterized Problems Based on Random Methods ⋮ An improved kernelization for \(P_{2}\)-packing ⋮ The complexity of perfect matchings and packings in dense hypergraphs ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ A \(5k\)-vertex kernel for \(P_2\)-packing
Cites Work
This page was built for publication: Maximum bounded \(H\)-matching is Max SNP-complete
