科研之友
微信
新浪微博
Facebook
分享链接
摘要
This paper presents a (10+epsilon)-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+epsilon (epsilon is an arbitrary positive number), while the second phase connects the dominating sets computed in the first phase, which has approximation ratio 4.
- 出版日期2009-8
- 单位新疆大学
