论文标题
单位磁盘图中的总统治
Total Domination in Unit Disk Graphs
论文作者
论文摘要
令$ g =（v，e）$为无向图。如果每个顶点$ v \ in v $中的每个顶点$ v \ in自身以外的$ d $，我们将$ d_t \ subseteq v $称为$ g $的总统治集（TDS）。在这里，我们考虑了单位磁盘图中的TDS问题，其中目的是为输入图找到最小的基数总统治设置。我们证明TDS问题是单位磁盘图中的NP-HARD。接下来，我们为问题提出了8个因子近似算法。提出的近似算法的运行时间为$ O（n \ log K）$，其中$ n $是输入图的顶点，$ k $是输出大小。我们还表明，TDS问题在单位磁盘图中接受PTA。
Let $G=(V,E)$ be an undirected graph. We call $D_t \subseteq V$ as a total dominating set (TDS) of $G$ if each vertex $v \in 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.
