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

MaRDI QIDQ3115271zbMATH OpenFDO

Authors D. S. Malyshev

Publication date 20 February 2012

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)

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

Cited in

(4)

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

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)