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

摘要

For a graph G = (V,E), a subset D is containnet in V is an r-hop dominating set if every vertex u ∈ V - D is at most r-hops away from D. It is a 2-connected r-hop dominating set if the subgraph of C 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.