A 5 +-approximation algorithm for minimum weighted dominating set in unit disk graph
A 5 +-approximation algorithm for minimum weighted dominating set in unit disk graph
复制标题
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Decheng Dai;Changyuan Yu
中科院分区：
文献类型：
--
作者：
Decheng Dai;Changyuan Yu
黄耀春，高晓峰，张钊，吴伟力，研究了加权单位圆盘图的最小权控制集问题，提出了一种近似比为5+的多项式时间算法，改进了之前的最佳结果6 + [j]。Optim。（issn: 1382-6905）（2008） 1573-2886。(印刷)(在线)]。结合上述文献中常用的技术，我们可以计算出近似比为9+的最小权连接支配集，超过了之前相同工作的最佳结果10+。©2008 Elsevier B.V.版权所有
We study the minimum weight dominating set problem in weighted unit disk graph, and give a polynomial time algorithm with approximation ratio 5+ , improving the previous best result of 6 + in [Yaochun Huang, Xiaofeng Gao, Zhao Zhang, Weili Wu, A better constant-factor approximation for weighted dominating set in unit disk graph, J. Comb. Optim. (ISSN: 1382-6905) (2008) 1573–2886. (Print) (Online)]. Combining the common technique used in the above mentioned reference, we can compute a minimum weight connected dominating set with approximation ratio 9+ , beating the previous best result of 10+ in the same work. © 2008 Elsevier B.V. All rights reserved.