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

DOI10.1134/S1990478917030115zbMath1399.05174OpenAlexW2753358546MaRDI QIDQ5374002

Dmitrii V. Sirotkin, Dmitriy 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

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

Related Items (2)

New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths ⋮ Unnamed Item

Cites Work

• On easy and hard hereditary classes of graphs with respect to the independent set problem
• On the maximum independent set problem in subclasses of subcubic graphs
• On the Maximum Independent Set Problem in Subclasses of Planar Graphs
• The Maximum Independent Set Problem in Planar Graphs
• Efficient Planarity Testing
• Local transformations of graphs preserving independence number
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• Unnamed Item
• Unnamed Item
• Unnamed Item

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