On Approximating Minimum 3-Connected m-Dominating Set Problem in Unit Disk Graph

摘要

Over years, virtual backbone has attracted lots of attention as a promising approach to deal with the broadcasting storm problem in wireless networks. Frequently, the problem of a quality virtual backbone is formulated as a variation of the minimum connected dominating set problem. However, a virtual backbone computed in this way is not resilient against topology change since the induced graph by the connected dominating set is one-vertex-connected. As a result, the minimum k-connected m-dominating set problem is introduced to construct a fault-tolerant virtual backbone. Currently, the best known approximation algorithm for the problem in unit disk graph by Wang assumes k≤3 and m≥1, and its performance ratio is 280 when k=m=3. In this paper, we use a classical result from graph theory, Tutte decomposition, to design a new approximation algorithm for the problem in unit disk graph for k≤3 and m≥1. In particular, the algorithm features with (a) a drastically simple structure and (b) a much smaller performance ratio, which is nearly 62 when k=m=3. We also conduct simulation to evaluate the performance of our algorithm.