Over years, many efforts are made for the problem of constructing quality fault-tolerant virtual backbones in wireless network. In case that a wireless network consists of physically equivalent nodes, e.g., with the same communication range, unit disk graph (UDG) is widely used to abstract the wireless network and the problem is formulated as the minimum k-connected m-dominating set problem on the UDG. So far, most results are focused on designing a constant factor approximation algorithm for this NP-hard problem under two positive integers k and m satisfying m ≥ k ≥ 1 and k ≤ 3. This paper introduces an approximation algorithm for the problem with m ≥ k ≥ 1. This algorithm is simple to implement; it connects the components by adding a bounded number of paths, which first computes a 1-connected m-dominating set D and repeats the following steps: (a) search the separators arbitrarily in (i - 1, m)-CDS with i = 2, 3, ⋯ , k, (b) add a bounded number of paths connecting the components separated by separators in (i-1, m)-CDS to improve the connectivity of (i-1, m)-CDS, until it becomes k-connected, and (c) remove redundant paths if there exist at every iteration. We provide a rigorous theoretical analysis to prove that the proposed algorithm is correct and its approximation ratio is a constant, for any fixed k.

This paper proposes a new polynomial time constant factor approximation algorithm for a more-a-decade-long open NP-hard problem, the minimum four-connected m-dominating set problem in unit disk graph (UDG) with any positive integer m ≥ 1 for the first time in the literature. We observe that it is difficult to modify the existing constant factor approximation algorithm for the minimum three-connected m-dominating set problem to solve the minimum four-connected m-dominating set problem in UDG due to the structural limitation of Tutte decomposition, which is the main graph theory tool used by Wang et al. to design their algorithm. To resolve this issue, we first reinvent a new constant factor approximation algorithm for the minimum three-connected m-dominating set problem in UDG and later use this algorithm to design a new constant factor approximation algorithm for the minimum four-connected m-dominating set problem in UDG.

Over years, many efforts are made for the problem of constructing quality fault-tolerant virtual backbones in wireless network. In case that a wireless network consists of physically equivalent nodes, e.g. with the same communication range, unit disk graph (UDG) is widely used to abstract the wireless network and the problem is formulated as the minimum k-connected mdominating set problem on the UDG. So far, most results are focused on designing a constant factor approximation algorithm for this NP-hard problem under two positive integers k and m satisfying m ≥ k ≥ 1 and k ≤ 3. Very recently, Shi et. al. and Fukunaga separately introduced constant factor approximation algorithms for the problem with m ≥ k ≥ 1. However, we found the structures of the algorithms are extremely complicated, and thus it would be difficult to implement and use them in practice. Motivated by such observation, this paper introduces a novel approximation algorithm for the problem with m ≥ k ≥ 1. This algorithm is based on our new technique which first computes a 1-connected m-dominating set D and repeatedly (a) decomposes D into an i-connected block tree, with i = 2, 3, ··· , k, and (b) use this graph structure to improve the connectivity of D, until D becomes k-connected. We provide a rigorous theoretical analysis to prove that the proposed algorithm is correct and its approximation ratio is a constant. We compare the structure of our algorithm against the existing ones and show our algorithm is much simpler to understand and implement.

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.

Over years, virtual backbone has attracted lots of attentions as a promising approach to deal with the broadcasting storm problem in wireless networks. One popular way to construct a quality virtual backbone is to solve 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 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 ≥ 3. In particular, the algorithm features with much simpler structure and much smaller performance ratio, e.g. nearly 66 when k = m = 3. We also conduct simulation to evaluate the performance of our algorithm.