The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem

DOI10.1515/dma-2013-017zbMath1311.05153OpenAlexW2331396760MaRDI QIDQ5249786

Dmitriy S. Malyshev

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

zbMATH Keywords

independent number\(H\)-packing number

Mathematics Subject Classification ID

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