Analysis of the influence of the number of edges on the complexity of the independent set problem

zbMATH Open1249.68089MaRDI QIDQ3115271FDOQ3115271

Authors: D. S. Malyshev 

Publication date: 20 February 2012

Recommendations

• Maximum independent sets near the upper bound
• Maximum independent sets in graphs of low degree
• The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
• The Maximum Independent Set Problem in Planar Graphs
• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs

zbMATH Keywords

computational complexityindependent set problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (4)

• On relating edges in graphs without cycles of length 4
• The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
• On edge-independent sets
• On the complexity of the independent set problem in triangle graphs

This page was built for publication: Analysis of the influence of the number of edges on the 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 Q3115271)