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

DOI10.1134/S199047891304008XzbMATH Open1324.05036MaRDI QIDQ5263816FDOQ5263816

D. S. Malyshev

Publication date: 17 July 2015

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

Recommendations

• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• scientific article
• 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

zbMATH Keywords

computational complexityefficient algorithmindependent set problemboundary class

Mathematics Subject Classification ID

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

Cited In (14)

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

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)