Classes of subcubic planar graphs for which the independent set problem is polynomially solvable

DOI10.1134/S199047891304008XMaRDI QIDQ5263816zbMATH OpenFDO

Authors D. S. Malyshev

Publication date 17 July 2015

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

zbMATH Keywords

computational complexityefficient algorithmindependent set problemboundary class

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• scientific article; zbMATH DE number 6004934
• On the maximum independent set problem in subclasses of planar graphs
• scientific article; zbMATH DE number 6460018
• On the maximum independent set problem in subclasses of subcubic graphs
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• The maximum independent set problem in subclasses of subcubic graphs
• The maximum independent set problem for cubic planar graphs
• NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs
• An approximation algorithm for the maximum independent set problem in cubic planar graphs

Cited in

(14)

• scientific article; zbMATH DE number 6460018 (Why is no real title available?)
• Independent sets in graphs without subtrees with many leaves
• Critical hereditary graph classes: a survey
• Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP
• A method of graph reduction and its applications
• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• Boundary classes for graph problems involving non-local properties
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• On integer programming with bounded determinants
• Computational complexity of the vertex cover problem in the class of planar triangulations
• scientific article; zbMATH DE number 7742928 (Why is no real title available?)
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems

This page was built for publication: Classes of subcubic planar graphs for which the independent set problem is polynomially solvable

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