Two algorithms for minimum 2-connected r-hop dominating set

For a graph G=(V,E)G=(V,E), a subset D⊆VD⊆V is an r  -hop dominating set if every vertex u∈V−Du∈V−D is at most r-hops away from D. It is a 2-connected r-hop dominating set if the subgraph of G induced by D is 2-connected. In this paper, we present two approximation algorithms to compute minimum 2-connected r-hop dominating set. The first one is a greedy algorithm using ear decomposition of 2-connected graphs. This algorithm is applicable to any 2-connected general graph. The second one is a three-phase algorithm which is only applicable to unit disk graphs. For both algorithms, performance ratios are given.

Research highlights
► A greedy approximation algorithm for 2-connected r  -hop dominating set (DS).
► An f(r)f(r)-approximation algorithm for 2-connected r-hop DS in unit disk graph.