A better constant-factor approximation for weighted dominating set in unit disk graph
✍ Scribed by Yaochun Huang; Xiaofeng Gao; Zhao Zhang; Weili Wu
- Publisher
- Springer US
- Year
- 2008
- Tongue
- English
- Weight
- 417 KB
- Volume
- 18
- Category
- Article
- ISSN
- 1382-6905
No coin nor oath required. For personal study only.
✦ Synopsis
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.