A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs
A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs
复制标题
DOI：
10.1007/11671411_23
复制
发表时间：
2005-10
期刊：
影响因子：
--
通讯作者：
T. Nieberg;J. Hurink
中科院分区：
文献类型：
--
作者：
T. Nieberg;J. Hurink
提出了一个求解单位圆盘图最小控制集问题的多项式时间近似方法。与以前已知的近似方案的最小支配集问题的单位盘图，我们的方法不假设的顶点的几何表示（指定在平面中的磁盘的位置）作为输入的一部分。PTAS的运行时间为nO（1/εlog 1/ε）。该算法接受任意无向图作为输入，并返回一个（1 +ε）-近似最小支配集，或者一个证明输入图不是单位圆盘图的证书，从而使算法具有鲁棒性. PTAS可以很容易地适用于其他类别的几何相交图。
We present a polynomial-time approximation scheme (PTAS) for the minimum dominating set problem in unit disk graphs. In contrast to previously known approximation schemes for the minimum dominating set problem on unit disk graphs, our approach does not assume a geometric representation of the vertices (specifying the positions of the disks in the plane) to be given as part of the input. The runtime of the PTAS isnO(1/εlog 1/ε). The algorithm accepts any undirected graph as input, and returns a (1 +ε)-approximate minimum dominating set, or a certificate showing that the input graph is no unit disk graph, making the algorithm robust. The PTAS can easily be adapted to other classes of geometric intersection graphs.