A better constant-factor approximation for weighted dominating set in unit disk graph
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.
unit disk graph connected dominating set wireless network