Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs

DOI10.1134/S1990478917030115MaRDI QIDQ5374002zbMATH OpenOpenAlexFDO

Authors Dmitrii V. Sirotkin, D. S. Malyshev

Publication date 6 April 2018

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

Full work available at URL https://doi.org/10.1134/s1990478917030115

zbMATH Keywords

efficient algorithmindependent set problemgraph reduction

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Paths and cycles (05C38)

Recommendations

• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• 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 Planar Graphs

Cites work

• scientific article; zbMATH DE number 6004934 (Why is no real title available?)
• scientific article; zbMATH DE number 3700235 (Why is no real title available?)
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• Efficient Planarity Testing
• Local transformations of graphs preserving independence number
• Maximum independent sets in graphs of low degree
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• On the maximum independent set problem in subclasses of planar graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• The Maximum Independent Set Problem in Planar Graphs

Cited in

(20)

• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• The Maximum Independent Set Problem in Planar Graphs
• scientific article; zbMATH DE number 7650229 (Why is no real title available?)
• New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
• scientific article; zbMATH DE number 7742928 (Why is no real title available?)
• NP-completeness of the independent dominating set problem in the class of cubic planar bipartite graphs
• A constructive existence theorem related to local transformations of graphs for the independent set problem
• Analysis of the influence of the number of edges on the complexity of the independent set problem
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A linear time algorithm for finding a maximum independent set of a fullerene
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• On the complexity of the independent set problem in triangle graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• scientific article; zbMATH DE number 6460018 (Why is no real title available?)
• An approximation algorithm for the maximum independent set problem in cubic planar graphs
• The maximum independent set problem for cubic planar graphs
• Independent sets in the graphs with bounded minors of the extended incidence matrix
• Independent sets in graphs without subtrees with many leaves
• On the maximum independent set problem in subclasses of planar graphs
• Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP

This page was built for publication: Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs

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