Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435530 | Theoretical Computer Science | 2011 | 5 Pages |
Abstract
In this paper, we investigate the positive influence dominating set (PIDS) which has applications in social networks. We prove that PIDS is APX-hard and propose a greedy algorithm with an approximation ratio of H(δ) where H is the harmonic function and δ is the maximum vertex degree of the graph representing a social network.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics