摘要： In this paper we consider a fundamental problem in the area of viral marketing, called Target Set Selection problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if G is a block-cactus graph, then the Target Set Selection problem can be solved in linear time, which generalizes Chen’s result (Discrete Math. 23:1400–1415, 2009 ) for trees, and the time complexity is much better than the algorithm in Ben-Zwi et al. (Discrete Optim., 2010 ) (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph G is a chordal graph with thresholds θ ( v )≤2 for each vertex v in G , then the problem can be solved in linear time. For a Hamming graph G having thresholds θ ( v )=2 for each vertex v of G , we precisely determine an optimal target set S for ( G , θ ). These results partially answer an open problem raised by Dreyer and Roberts (Discrete Appl. Math. 157:1615–1627, 2009 ). 其他題名： J Comb Optim 出版者： Boston: Springer US 出版日期： 2013-05-01 出處： Journal of combinatorial optimization, 2013-05, Vol.25 (4), p.702-715 版權： Springer Science+Business Media, LLC 2012 識別號： ISSN: 1382-6905 識別號： EISSN: 1573-2886 識別號： DOI: 10.1007/s10878-012-9518-3
