| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427459 | Information Processing Letters | 2010 | 6 Pages |
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.
