Approximation Algorithms for the Connected Dominating Set Problem in Unit Disk Graphs

The connected dominating set (CDS) problem, which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs (UDGs). This paper focuses on the CDS problem in wireless networks. Investigation of some properties of independent set (IS) in UDGs shows that geometric features of nodes distribution like angle and area can be used to design efficient heuristics for the approximation algorithms. Several constant factor approximation algorithms are presented for the CDS problem in UDGs. Simulation results show that the proposed algorithms perform better than some known ones.