Abstract | ||
---|---|---|
For a graph G = (V, E), a vertex set C subset of V is an m-f old outer-connected dominating set (m-f old OCDS) 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 OCDS in general graphs, which returns a solution of size at most alpha + 1+ln(Delta + m + 1) times that of aminimum m-fold OCDS, where Delta is the maximum degree of the graph and alpha is a positive number at most Delta+m+1. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1007/s10878-020-00668-z | JOURNAL OF COMBINATORIAL OPTIMIZATION |
Keywords | DocType | Volume |
m-Fold outer-connected dominating set, Potential function, Greedy algorithm, Submodular | Journal | 41 |
Issue | ISSN | Citations |
1 | 1382-6905 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xiaozhi Wang | 1 | 0 | 0.34 |
Xianyue Li | 2 | 0 | 0.68 |
Bo Hou | 3 | 0 | 1.69 |
Wen Liu | 4 | 8 | 3.34 |
Lidong Wu | 5 | 0 | 0.34 |
Suogang Gao | 6 | 0 | 2.03 |