On positive influence dominating sets in social networks

Feng Wang, Hongwei Du, Erika Camacho, Kuai Xu, Wonjun Lee, Yan Shi, Shan Shan

Research output: Contribution to journalArticlepeer-review

73 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)265-269
Number of pages5
JournalTheoretical Computer Science
Issue number3
Publication statusPublished - 2011 Jan 21

Bibliographical note

Funding Information:
✩ This research was jointly supported by MEST, Korea under WCU (R33-2008-000-10044-0), and National Science Foundation of USA under grants


  • APX-hard
  • Dominating set
  • Positive influence dominating set
  • Social networks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On positive influence dominating sets in social networks'. Together they form a unique fingerprint.

Cite this