scientific article; zbMATH DE number 6460018

MaRDI QIDQ5263782zbMATH OpenFDO

Authors D. S. Malyshev

Publication date 17 July 2015

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

zbMATH Keywords

computational complexitypolynomial algorithmindependent set problem

Mathematics Subject Classification ID

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

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; zbMATH DE number 6004934
• 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

Cited in

(6)

• Independent set in \(P_5\)-free graphs in polynomial time
• A sufficient condition to extend polynomial results for the maximum independent set problem
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
• Two cases of polynomial-time solvability for the coloring problem
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems

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)