Approximation Algorithms For The Fault-tolerant Connected Dominating Set In A General Graph

Using a connected dominating set(CDS) to serve as the virtual backbone of a wireless network is an effective way to save energy and alleviate broadcasting storm. Since nodes may fail due to an accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a k-connected m-fold dominating set((k, m)-CDS for short). A subset of nodes C ? V(G) is a(k, m)-CDS of G if every node in V(G)\C is adjacent with at least m nodes in C and the subgraph of G induced by C is k-connected.In this paper, we study approximation algorithms for(k, m)-CDS while k = 1 and k = 3, m ≥ 3. In Chapter 1, we introduce the background and some related works. In Chapter 2, we present an approximation algorithm for the minimum(1, m)-CDS problem in a general graph, the approximation ratio is 2+ln(?+m-2), where ? is the maximum degree of the graph. This result improves on the previous best known performance ratio of 2H(? + m- 1) for this problem, where H(·) is the Harmonic number, and the approximation ratio is asymptotically tight. In Chapter 3, we present an approximation algorithm for the minimum(3, m)-CDS(m ≥ 3) problem in a general graph, achieving approximation ratio O(ln n). This is the ?rst algorithm for the minimum(3, m)-CDS problem in a general graph. In Chapter 4, we concludes this paper and discusses some future research directions.