On positive influence dominating sets in social networks

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

doi:10.1016/j.tcs.2009.10.001

상세 보기

On positive influence dominating sets in social networks

Wang, Feng;
Du, Hongwei;
Camacho, Erika;
Xu, Kuai;
Lee, Wonjun;
외 2명

Citations

WEB OF SCIENCE

76

초록

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.

키워드

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

제목: On positive influence dominating sets in social networks

저자: Wang, Feng; Du, Hongwei; Camacho, Erika; Xu, Kuai; Lee, Wonjun; Shi, Yan; Shan, Shan

DOI: 10.1016/j.tcs.2009.10.001

발행일: 2011-01-21

유형: Article; Proceedings Paper

저널명: Theoretical Computer Science

권: 412

호: 3

페이지: 265 ~ 269