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-017MaRDI QIDQ5249786zbMATH OpenOpenAlexFDO

Authors D. 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)

Recommendations

• Analysis of the influence of the number of edges on the complexity of the independent set problem
• The complexity of some problems on maximal independent sets in graphs
• On the complexity of the independent set problem in triangle graphs
• Independent packings in structured graphs
• On the complexity of digraph packings
• On the complexity of approximating the independent set problem
• The complexity of perfect packings in dense graphs
• Computing independent sets in graphs with large girth
• On the complexity of approximating the independent set problem (extended abstract)
• Packing parameters in graphs: new bounds and a solution to an open problem

Cited in

(5)

• On König graphs with respect to P₄
• König graphs with respect to the 4-path and its spanning supergraphs
• A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs
• On integer programming with bounded determinants
• Analysis of the influence of the number of edges on the complexity of the independent set problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5249786)