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-017zbMATH Open1311.05153OpenAlexW2331396760MaRDI QIDQ5249786FDOQ5249786
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
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cited In (5)
- On König graphs with respect to \(P_4\)
- 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
- Analysis of the influence of the number of edges on the complexity of the independent set problem
- On integer programming with bounded determinants
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)
