The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
From MaRDI portal
Publication:5249786
DOI10.1515/dma-2013-017zbMath1311.05153OpenAlexW2331396760MaRDI QIDQ5249786
Publication date: 12 May 2015
Published in: Discrete Mathematics and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1515/dma-2013-017
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (4)
On integer programming with bounded determinants ⋮ A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs ⋮ On König graphs with respect to P4 ⋮ König Graphs with Respect to the 4-Path and Its Spanning Supergraphs
This page was built for publication: The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem