Connected Dominating Set: Theory and Applications
The connected dominating set (CDS) has been a classic subject studied in graph theory since 1975. It has been discovered in recent years that CDS has important applications in communication networks —especially in wireless networks —as a vi
- PDF / 568,601 Bytes
- 28 Pages / 439.36 x 666.15 pts Page_size
- 4 Downloads / 261 Views
CDS in Unit Disk Graph
Every dance is kind of fever chart, a graph of the heart. M ARTHA GRAHAM
3.1 Motivation and Overview A unit disk is a disk with diameter one. Denote by diskr (o) the disk with center o and radius r. A graph G = (V, E) is called a unit disk graph if it can be embedded into the Euclidean plane such that an edge between two nodes u and v exists if and only if disk0.5 (u) ∩ disk0.5 (v) = 0, / that is, their Euclidean distance d(u, v) ≤ 1. The unit disk graph is a mathematical model for wireless sensor networks when all sensors have the same communication radius. For any node v of a unit disk graph G, the neighborhood area of v is the disk disk1 (v). For any subset V of nodes, the neighborhood area of V is the union of disks, ∪v∈V disk1 (v). For any subgraph H, the neighborhood area of H is the union of disks, ∪v∈V (H) disk1 (v) where V (H) is the node set of subgraph H. Clearly, in a unit disk graph, two nodes u and v are independent if and only if d(u, v) > 1. For any two points u and v in the Euclidean plane, if d(u, v) > 1, then u and v are also said to be independent. The boundary of an area Ω is denoted by ∂ Ω. Thus, ∂ diskr (v) = circler (v), which is the circle with radius r and center v. Clark, Colbourn, and Johnson [24] proved that MIN-CDS in unit disk graphs is still NP-hard. Wan et al. [104] first found that MIN-CDS has polynomial-time constant-approximations. Cheng et al. [22] designed the first PTAS. Since the running time of PTAS is a polynomial of a high degree, which is hard to implement, the design of fast polynomial-time constant-approximation is still an active research topic in the literature [14, 21, 51, 72, 75, 79, 104, 106]. There are many designs using the approach initiated by Wan et al. [104]: At the first stage, construct a maximal independent set. At the second stage, connect the maximal independent set into a CDS. D.-Z. Du and P.-J. Wan, Connected Dominating Set; Theory and Applications, Springer Optimization and Its Applications 77, DOI 10.1007/978-1-4614-5242-3 3, © Springer Science+Business Media New York 2013
35
36
3 CDS in Unit Disk Graph
Fig. 3.1 The neighborhood of n(≥ 3) linear points with consecutive distance one may contain 3n + 3 independent points
To analyze such two-stage algorithms, one needs to know what is the maximum size of a maximal independent set (i.e., the size of the maximum independent set) compared with the size of the minimum CDS. The size of the maximum independent set in a graph G is called the independent number, denoted by α (G). The size of the minimum CDS in G is called the connected dominating number, denoted by γc (G). Wan et al. [106] indicated that there exist some connected unit disk graphs G such that
α (G) = 3 · γc (G) + 3 (Fig. 3.1). Many researchers believe that for every connected unit disk graph G
α (G) ≤ 3 · γc (G) + 3.
(3.1)
Many efforts have been made to attack this upper bound. They can be classified into classes based on the difference of basic approaches. One is based on the study of packing independe
Data Loading...
