MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
Deying Li, Lin Liu, Huiqiang Yang · Discrete Mathematics Algorithms and Applications · 2009
In this paper, we study the connected r-hop k-dominating set problem in wireless networks. We propose two algorithms for the problem. We prove that algorithm I for UDG has (2r + 1) 3 approximate ratio for k ≤ (2r + 1) 2 and (2r + 1)((2r + 1) 2 + 1)-approximate ratio for k > (2r + 1) 2 . And algorithm II for any undirected graph has (2r + 1) ln (Δ r ) approximation ratio, where Δ r is the largest cardinality among all r-hop neighborhoods in the network. The simulation results show that our algorithms are efficient.