Two Algorithms For Minimum 2-Connected R-Hop Dominating Set

With the rapid development of information networks, many correlative theoreticproblems draw more and more attention of researchers. A wireless sensor network consistsof a huge amount of sensors, which collaborate to sense, collect, and process the raw in-formation of the phenomenon in the sensing area, and transmit the processed informationto the observers. If every sensor broadcasts every message it receives all the time, a lotof troubles may be caused. First, it is a waste of energy. Furthermore, it may cause theso-called broadcast storm. To alleviate such problems, the concept of virtual backbonewas proposed for packet routing and control in wireless networks.The underlying topology of a network can be modeled as a graph. In a graph G =(V,E), a dominating set (DS) is a vertex set D ? V such that every vertex u in V (?) Dis adjacent with at least one vertex in D. For a vertex set U ? V , denote by G[U] thesubgraph of G induced by U. A dominating set D is a connected dominating set (CDS) ofG if G[D] is connected. For a positive integer r, a vertex u is said to be r-hop dominatedby a vertex set U if u is at most r-hops away from some vertex in U. A subset D of V isa r-hop dominating set (r-hop DS) if every vertex u∈V \ D is r-hop dominated by D.This thesis is divided into three chapters. In chapter 1, we introduce the backgroundof our study, and state the main results in this thesis. In chapter 2, we present a greedyalgorithm to compute a minimum 2-connected r-hop dominating set. The basic idea ofour algorithm is to make use of the ear decomposition of 2-connected graphs. It shouldbe noted that the algorithm is applicable to any general graph. In chapter 3, we givea three-phase approximation algorithm to compute a 2-connected r-hop DS in a unitdisk graph. In this algorithm, we make use of the fact that a graph G of order at leastthree is 2-connected if and only if the number of its blocks is one. For both algorithms,performance ratios are given.