|
Abstract
|
The influence maximization is an important problem in study of social networks.
In 2007, Bharathi, Kempe and Salek conjectured that the influence maximization problem is NP-hard for arborescences directed into a root. Recently, this conjecture is proved for the IC model and disproved for the LT model. This is the first result to tell the difference on computational complexity between two important diffusion models, the IC model and the LT model in social networks.
|
|
Affiliation
|
Dingzhu Du received his MS degree in operations research from Inst. of Applied Math., CAS in 1982, and PhD degree in math from Univ. of California at Santa Barbara in 1985.
He is the founding editor-in-chief of J. of Combinatorial Optimization, Discrete Math., Algorithms and Applications, Computational Social Networks. He received CSTS Prize from INFORMS in 1998 for his research excellence in the interface between operations research and computer science. He received the 2nd Prize of National Nature Science of China in 1996 and the Award of National Young Scientist of China in 1992.
|
