A better constant-factor approximation for weighted dominating set in unit disk graph |
| |
| Authors: | Yaochun Huang Xiaofeng Gao Zhao Zhang Weili Wu |
| |
| Affiliation: | (1) Department of Computer Science, University of Texas at Dallas, Richardson, USA;(2) College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang, China |
| |
| Abstract: | This paper presents a (10+ε)-approximation algorithm to compute minimum-weight connected dominating set (MWCDS) in unit disk graph. MWCDS is to select a vertex subset with minimum weight for a given unit disk graph, such that each vertex of the graph is contained in this subset or has a neighbor in this subset. Besides, the subgraph induced by this vertex subset is connected. Our algorithm is composed of two phases: the first phase computes a dominating set, which has approximation ratio 6+ε (ε is an arbitrary positive number), while the second phase connects the dominating sets computed in the first phase, which has approximation ratio 4. This work is supported in part by National Science Foundation under grant CCF-9208913 and CCF-0728851; and also supported by NSFC (60603003) and XJEDU. |
| |
| Keywords: | Wireless network Connected dominating set Unit disk graph |
| 本文献已被 SpringerLink 等数据库收录！ |
|
