Approximation Algorithms for the Connected Dominating Set Problem in Unit Disk Graphs

作     者：Gang Lu Ming-Tian Zhou Yong Tang Ming-Yuan Zhao Xin-Zheng Niu Kun She 

作者机构：School of Computer Science and Engineering University of Electronic Science and Technology of China Chengdu 610054 China 

出 版 物：《Journal of Electronic Science and Technology of China》 (中国电子科技（英文版）)

年 卷 期：2009年第7卷第3期

页      面：214-222页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：supported by the National Natural Science Foundation of China under Grant No 60473090 the National "11th Five-Year-Supporting-Plan" of China under Grant No 2006BAH02A0407 

主　　题：Approximation algorithm connecteddominating set unit disk graph 

摘      要：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.