Some results on the target set selection problem

Chun-Ying Chiang, Liang-Hao Huang, Bo-Jr Li, Jiaojiao Wu and Hong-Gwa Yeh ()
Additional contact information
Chun-Ying Chiang: National Central University
Liang-Hao Huang: National Central University
Bo-Jr Li: National Sun Yat-sen University
Jiaojiao Wu: National Sun Yat-sen University
Hong-Gwa Yeh: National Central University

Journal of Combinatorial Optimization, 2013, vol. 25, issue 4, No 17, 702-715

Abstract: Abstract 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).

Keywords: Target set selection; Viral marketing; Tree; Block graph; Block-cactus graph; Chordal graph; Hamming graph; Social networks; Diffusion of innovations; Viral marketing; Dynamic monopoly; Irreversible spread of influence (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9518-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:25:y:2013:i:4:d:10.1007_s10878-012-9518-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9518-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().