Construction of strongly connected dominating sets in asymmetric multihop wireless networks

Consider an asymmetric wireless network represented by a digraph G=(V,E). A subset of vertices U is called a strongly connected dominating set (SCDS) if the subgraph induced by U is strongly connected and every vertex not in U has both an in-neighbor in U and an out-neighbor in U. SCDS plays an important role of the virtual backbone in asymmetric wireless networks. Motivated by the construction of a small virtual backbone, we study the problem Minimum SCDS, which seeks a smallest SCDS of a digraph. For any constant 0<ρ<1, there is no polynomial-time ρlnn-approximation for Minimum SCDS unless NP⊆DTIME(no(lnn)), where n is the number of nodes. However, none of the polynomial-time heuristics for Minimum SCDS proposed in the literature are logarithmic approximations. In this paper, we present a polynomial-time (3H(n−1)−1)-approximation algorithm for Minimum SCDS, where H is the harmonic function. The approximation ratio of this algorithm is thus within a factor of 3 from the best possible approximation ratio achievable by any polynomial-time algorithm.