A Constant-Factor Approximation for d-Hop Connected Dominating Sets in Unit Disk Graph
Finding a d-hop connected dominating set (d-CDS) in a wireless network is very important to help constructing a well organized, hierarchical based network structure. d-CDS is a vertex subset of a given graph, such that every vertex in this graph is either contained in this subset or we can find another vertex in the subset at most d hops away from this vertex. Besides, the subgraph induced by this subset is connected. People always discuss such problem under unit disk graph (UDG) because of the special characteristics of wireless networks. Previous literatures proposed several heuristic algorithms for d-CDS, with numerical examples and comparison statistics. However, they all lacked approximation analysis, especially for the quality of their approximate solutions. Till now, none of them gave an approximation algorithm with performance ratios.
Wireless Network d-Hop Connected Dominat-ing Set Unit Disk Graph
Xiaofeng Gao Xianyue Li Weili Wu
Department of Computer Science & Engineering, Shanghai Jiao Tong University, China School of Mathematics and Statistics, Lanzhou University, China Department of Computer Science, University of Texas at Dallas, USA
国际会议
The Tenth International Conference on Information and Management Sciences(IMS)(第十届信息与管理科学国际会议)
拉萨
英文
263-272
2011-08-06（万方平台首次上网日期，不代表论文的发表时间）