On positive influence dominating sets in social networks
- Authors
- Wang, Feng; Du, Hongwei; Camacho, Erika; Xu, Kuai; Lee, Wonjun; Shi, Yan; Shan, Shan
- Issue Date
- 21-1월-2011
- Publisher
- ELSEVIER
- Keywords
- Dominating set; Positive influence dominating set; Social networks; APX-hard
- Citation
- THEORETICAL COMPUTER SCIENCE, v.412, no.3, pp.265 - 269
- Indexed
- SCIE
SCOPUS
- Journal Title
- THEORETICAL COMPUTER SCIENCE
- Volume
- 412
- Number
- 3
- Start Page
- 265
- End Page
- 269
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/113254
- DOI
- 10.1016/j.tcs.2009.10.001
- ISSN
- 0304-3975
- 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(delta) where H is the harmonic function and delta is the maximum vertex degree of the graph representing a social network. (C) 2009 Elsevier B.V. All rights reserved.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - School of Cyber Security > Department of Information Security > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.