scientific article; zbMATH DE number 6460018

zbMATH Open1324.05142MaRDI QIDQ5263782FDOQ5263782

Authors: D. S. Malyshev 

Publication date: 17 July 2015

Full work available at URL: http://mathnet.ru/eng/da698

Title of this publication is not available (Why is that?)

Recommendations

• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• scientific article; zbMATH DE number 6460010
• New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
• scientific article
• Independent domination in finitely defined classes of graphs: polynomial algorithms
• scientific article; zbMATH DE number 7742928
• On the independent domination polynomial of a graph
• Structural Information and Communication Complexity
• Optimal graphs for independence and \(k\)-independence polynomials

zbMATH Keywords

computational complexitypolynomial algorithmindependent set problem

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (4)

• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• A sufficient condition to extend polynomial results for the maximum independent set problem
• Two cases of polynomial-time solvability for the coloring problem

This page was built for publication:

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