Name
Abstract | ||
|---|---|---|
Consider a graph \(G=(V,E)\) and a vertex subset \(A \subseteq V\). A vertex v is positive-influence dominated by A if either v is in A or at least half the number of neighbors of v belong to A. For a target vertex subset \(S \subseteq V\), a vertex subset A is a positive-influence target-dominating set for target set S if every vertex in S is positive-influence dominated by A. Given a graph G and a target vertex subset S, the positive-influence target-dominating set (PITD) problem is to find the minimum positive-influence dominating set for target S. In this paper, we show two results: (1) The PITD problem has a polynomial-time \((1 + \log \lceil \frac{3}{2} \Delta \rceil )\)-approximation in general graphs where \(\Delta \) is the maximum vertex-degree of the input graph. (2) For target set S with \(|S|=\Omega (|V|)\), the PITD problem has a polynomial-time O(1)-approximation in power-law graphs. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s11590-015-0938-8 | Optimization Letters |
Keywords | Field | DocType |
Positive-influence, Target-dominating, Social networks | Discrete mathematics,Graph,Dominating set,Combinatorics,Vertex (geometry),Omega,Mathematics | Journal |
Volume | Issue | ISSN |
11 | 2 | 1862-4480 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guangmo Tong | 1 | 71 | 10.47 |
| Weili Wu | 2 | 2093 | 170.29 |
| Panos M. Pardalos | 3 | 3720 | 397.84 |
| Ding-Zhu Du | 4 | 3497 | 283.06 |