Let G = (V, E) be a simple graph. A set D ∈ V is called a vertex-edge dominating set of G if for each edge e = (u, v) ∈ E, either u or v is in D or one vertex from their neighbor is in D. Simply, a vertex v ∈ V, vertex-edge dominates every edge (u,v), as well as every edge adjacent to these edges. The vertex-edge dominating problem is to find a minimum vertex-edge dominating set of G. Herein, we study the vertex-edge dominating set problem in unit disk graphs and prove that this problem is NP-hard in that class of graphs. We also show that the problem admits a polynomial time approximation scheme (PTAS) in unit disk graphs.
展开▼
