A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs
A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs
复制标题
单位圆盘图上具有平滑权重的最小加权支配集问题的 PTAS
DOI：
10.1007/s10878-010-9357-z
复制
发表时间：
2012-05
影响因子：
1
通讯作者：
Wu, Weili
中科院分区：
文献类型：
--
作者：
Zhu, Xu;Wang, Wei;Shan, Shan;Wang, Zhong;Wu, Weili
在最小加权支配集问题(MWDS)中，给出了一个在每个顶点上具有非负权的单位圆盘图。MWDS寻找具有最小总权的图的顶点的子集，使得图的每个顶点要么在该子集中，要么与该子集中的一些节点相邻。如果任意两个相邻节点的权重之比的上界为一个常数，则该权函数称为光滑函数。众所周知，MWDS是NP难的。在这篇文章中，我们给出了单位圆盘图上具有光滑权的MWD的第一多项式时间逼近格式(PTAS)，它对任意ε>；0实现了MWD的(1+ε)-逼近。
In the minimum weighted dominating set problem (MWDS), we are given a unit disk graph with non-negative weight on each vertex. The MWDS seeks a subset of the vertices of the graph with minimum total weight such that each vertex of the graph is either in the subset or adjacent to some nodes in the subset. A weight function is called smooth, if the ratio of the weights of any two adjacent nodes is upper bounded by a constant. MWDS is known to be NP-hard. In this paper, we give the first polynomial time approximation scheme (PTAS) for MWDS with smooth weights on unit disk graphs, which achieves a (1+ε)-approximation for MWDS, for anyε>0.
登录
查看更多内容
DOI：
10.1007/11671411_23
发表时间：
2005-10
期刊：
--
影响因子：
--
作者：
T. Nieberg;J. Hurink
通讯作者：
T. Nieberg;J. Hurink
影响因子：
3.8
作者：
P. Wan;K. Alzoubi;O. Frieder
通讯作者：
P. Wan;K. Alzoubi;O. Frieder
影响因子：
9.5
作者：
Yang Wang;Weizhao Wang;Xiangyang Li
通讯作者：
Yang Wang;Weizhao Wang;Xiangyang Li
影响因子：
0.8
作者：
CLARK, BN;COLBOURN, CJ;JOHNSON, DS
通讯作者：
JOHNSON, DS
DOI：
--
发表时间：
2009
期刊：
--
影响因子：
--
作者：
Decheng Dai;Changyuan Yu
通讯作者：
Decheng Dai;Changyuan Yu