Computational complexity of the vertex cover problem in the class of planar triangulations
From MaRDI portal
Publication:1744983
DOI10.1134/S0081543817090139zbMath1388.05049OpenAlexW2789978531MaRDI QIDQ1744983
Publication date: 20 April 2018
Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s0081543817090139
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)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum independent sets in 3- and 4-regular Hamiltonian graphs
- On rigid circuit graphs
- Higher-order triangular-distance Delaunay graphs: graph-theoretical properties
- Realizability of Delaunay triangulations
- Recent developments on graphs of bounded clique-width
- A partial k-arboretum of graphs with bounded treewidth
- Graph-theoretical conditions for inscribability and Delaunay realizability
- On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
- Face covers and the genus problem for apex graphs
- The maximum independent set problem in subclasses of subcubic graphs
- Triangulating with high connectivity.
- Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
- Geometric Spanner Networks
- Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
- PROXIMITY GRAPHS: E, δ, Δ, χ AND ω
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
This page was built for publication: Computational complexity of the vertex cover problem in the class of planar triangulations
