A greedy algorithm for the fault-tolerant outer-connected dominating set problem
- PDF / 329,934 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 52 Downloads / 184 Views
A greedy algorithm for the fault-tolerant outer-connected dominating set problem Xiaozhi Wang1 · Xianyue Li2 · Bo Hou1 · Wen Liu1 · Lidong Wu3 · Suogang Gao1 Accepted: 1 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract For a graph G = (V , E), a vertex set C ⊆ V is an m- f old outer -connected dominating set (m- f old OC DS) of G if every vertex in V \C has at least m neighbors in C and the subgraph of G induced by V \C is connected. In this paper, we present a greedy algorithm to compute an m-fold OC DS in general graphs, which returns a solution of size at most α +1+ln(+m +1) times that of a minimum m-fold OC DS, where is the maximum degree of the graph and α is a positive number at most +m+1. Keywords m-Fold outer-connected dominating set · Potential function · Greedy algorithm · Submodular
1 Introduction Let G = (V , E) be a simple connected graph, where V and E are the vertex set and the edge set of G, respectively. Given a vertex v ∈ V , the sets N G (v) = {u ∈ V | uv ∈ E} and N G [v] = N G (v) ∪ {v} denote the neighbor hood and the closed neighbor hood of v in G, respectively. The size of N G (v) is called the degr ee of v, denoted by dG (v). We call = max{dG (v) | v ∈ V } the maximum degr ee of G.
B
Suogang Gao [email protected] Lidong Wu [email protected]; [email protected]
1
School of Mathematics Science, Hebei Normal University, Shijiazhuang 050024, People’s Republic of China
2
School of Mathematics and statistics, Lanzhou University, Lanzhou 730000, People’s Republic of China
3
Department of Computet Science, University of Texas at Tyler, Tyler, USA
123
Journal of Combinatorial Optimization
For a graph G = (V , E), a subset C of V is said to be a dominating set (DS) of G if every vertex v ∈ V \C has a neighbor in C. Vertices in C are called dominator s and vertices in V \C are called dominatees. The domination number of a graph G, denoted by γ (G), is the minimum cardinality of a dominating set of G. The concept of domination has been extensively studied, both in structural and algorithmic graph theory, because of its numerous applications to a variety of areas. The two books (Haynes et al. 1998a, b) show us plenty of results and applications of domination in graphs. Many variants of the basic concepts of domination have appeared in literature due to different applications. A connected dominating set (C DS) is a DS C such that G[C], the subgraph of G induced by C, is connected. To save energy and reduce interference, it is desirable that the C DS is as small as possible. Sometimes, a simple C DS cannot meet people’s expectation due to frequent vertex failures, which are inherent in wireless sensor networks (WSNs). To make a virtual backbone more robust, people suggest using (k, m)-C DS. A vertex subset C is a k-connected m- f old dominating set ((k, m)C DS), if every vertex in V \C has at least m-neighbors in C and G[C] is k-connected. By the definition, in order that message can be shared by the whole network, every vertex in V \C can to
Data Loading...
