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

DOI10.1134/S1990478917030115zbMATH Open1399.05174OpenAlexW2753358546MaRDI QIDQ5374002FDOQ5374002

Authors: Dmitrii V. Sirotkin, D. S. Malyshev Error creating thumbnail:

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

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

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)

Cites Work

• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Efficient Planarity Testing
• The Maximum Independent Set Problem in Planar Graphs
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• Maximum independent sets in graphs of low degree
• On the maximum independent set problem in subclasses of subcubic graphs
• On the maximum independent set problem in subclasses of planar graphs
• Local transformations of graphs preserving independence number
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (20)

• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• The Maximum Independent Set Problem in Planar Graphs
• Title not available (Why is that?)
• New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
• Title not available (Why is that?)
• 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
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Analysis of the influence of the number of edges on the complexity of the independent set problem
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• A linear time algorithm for finding a maximum independent set of a fullerene
• On the complexity of the independent set problem in triangle graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• Title not available (Why is that?)
• 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)