• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

On positive-influence target-domination

Optimization Letters. 2017. Vol. 11. No. 2. P. 419-427.
Tong G., Wu W., Pardalos P. M., Du D.

Consider a graph G = (V, E) and a vertex subset A ⊆ 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 ⊆ 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[3/2*Delta])-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.