中国电子科技2009，Vol.7Issue(3)：214-222,9.
Approximation Algorithms for the Connected Dominating Set Problem in Unit Disk Graphs
Approximation Algorithms for the Connected Dominating Set Problem in Unit Disk Graphs
摘要
Abstract
The connected dominating set (CDS) problem, which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs (UDGs). This paper focuses on the CDS problem in wireless networks. Investigation of some properties of independent set (IS) in UDGs shows that geometric features of nodes distribution like angle and area can be used to design efficient heuristics for the approximation algorithms. Several constant factor approximation algorithms are presented for the CDS problem in UDGs. Simulation results show that the proposed algorithms perform better than some known ones.关键词
Approximation algorithm/ connected dominating set/ unit disk graph.Key words
Approximation algorithm/ connected dominating set/ unit disk graph.引用本文复制引用
Gang Lu,Ming-Tian Zhou,Yong Tang,Ming-Yuan Zhao,Xin-Zheng Niu,Kun She..Approximation Algorithms for the Connected Dominating Set Problem in Unit Disk Graphs[J].中国电子科技,2009,7(3):214-222,9.基金项目
This work was supported by the National Natural Science Foundation of China under Grant No. 60473090, and the National "11th Five-Year- Supporting-Plan" of China under Grant No. 2006BAH02A0407. （）
