Computational Complexity of the Vertex Cover Problem in the Class of Planar Triangulations |
| |
Authors: | K S Kobylkin |
| |
Institution: | 1.Krasovskii Institute of Mathematics and Mechanics,Ural Branch of the Russian Academy of Sciences,Yekaterinburg,Russia;2.Ural Federal University,Yekaterinburg,Russia |
| |
Abstract: | We study the computational complexity of the vertex cover problem in the class of planar graphs (planar triangulations) admitting a plane representation whose faces are triangles. It is shown that the problem is strongly NP-hard in the class of 4-connected planar triangulations in which the degrees of vertices are of order O(log n), where n is the number of vertices, and in the class of plane 4-connected Delaunay triangulations based on the Minkowski triangular distance. A pair of vertices in such a triangulation is adjacent if and only if there is an equilateral triangle ?(p, λ) with p ∈ R2 and λ > 0 whose interior does not contain triangulation vertices and whose boundary contains this pair of vertices and only it, where ?(p, λ) = p + λ? = {x ∈ R2: x = p + λa, a ∈ ?}; here ? is the equilateral triangle with unit sides such that its barycenter is the origin and one of the vertices belongs to the negative y-axis. Keywords: computational complexity, Delaunay triangulation, Delaunay TD-triangulation. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|