A method of graph reduction and its applications

DOI10.1515/dma-2018-0022zbMath1394.05094OpenAlexW2888414688MaRDI QIDQ1669583

Dmitrii V. Sirotkin, Dmitriy S. Malyshev

Publication date: 3 September 2018

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma-2018-0022

zbMATH Keywords

computational complexityplanar graphindependent setsplanar triangulation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• On the maximum independent set problem in subclasses of subcubic graphs
• On the Maximum Independent Set Problem in Subclasses of 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