Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs

Connected dominating set (CDS) in unit disk graphs has a wide range of applications in wireless ad hoc networks. A number of approximation algorithms for constructing a small CDS in unit disk graphs have been proposed in the literature. The majority of these algorithms follow a general two‐phased approach. The first phase constructs a dominating set, and the second phase selects additional nodes to interconnect the nodes in the dominating set. In the performance analyses of these two‐phased algorithms, the relation between the independence number α and the connected domination number γ c of a unit‐disk graph plays the key role. The best‐known relation between them is $\alpha \le 3\frac{2}{3}{\gamma }_c+1$ . In this paper, we prove that α≤3.4306γ c +4.8185. This relation leads to tighter upper bounds on the approximation ratios of two approximation algorithms proposed in the literature.