On positive influence dominating sets in social networks期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

On positive influence dominating sets in social networks

Authors:	Feng Wang Hongwei Du

Affiliation:	^a Division of Mathematical and Natural Sciences, Arizona State University, Phoenix, AZ 85069, USA ^b Department of Computer Science, Illinois Institute of Technology, Chicago, IL 60616, USA ^c Division of Computer and Communication Engineering, Korea University, Seoul, Republic of Korea ^d Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA

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.

Keywords:	Dominating set Positive influence dominating set Social networks APX-hard
本文献已被 ScienceDirect 等数据库收录！