查看文章

In this paper, we study the problem of computing quality fault-tolerant virtual backbone in homogeneous wireless network, which is defined as the -connected -dominating set problem in a unit disk graph. This problem is NP-hard, and thus many efforts have been made to find a constant factor approximation algorithm for it, but never succeeded so far with arbitrary and pair. We propose a new strategy for computing a smaller-size 3-connected -dominating set in a unit disk graph with any . We show the approximation ratio of our algorithm is constant and its running time is polynomial. We also conduct a simulation to examine the average performance of our algorithm. Our result implies that while there exists a constant factor approximation algorithm for the -connected -dominating set problem with arbitrary and pair, the -connected -dominating set problem is still open with …