A method of graph reduction and its applications
From MaRDI portal
Publication:1669583
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
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