Total Domination in Unit Disk Graphs
share
Let G=(V,E) be an undirected graph. We call D_t ⊆ V as a total dominating set (TDS) of G if each vertex v ∈ V has a dominator in D other than itself. Here we consider the TDS problem in unit disk graphs, where the objective is to find a minimum cardinality total dominating set for an input graph. We prove that the TDS problem is NP-hard in unit disk graphs. Next, we propose an 8-factor approximation algorithm for the problem. The running time of the proposed approximation algorithm is O(n log k), where n is the number of vertices of the input graph and k is output size. We also show that TDS problem admits a PTAS in unit disk graphs.
READ FULL TEXT