Some results on the target set selection problem

Please use this identifier to cite or link to this item: https://ir.lib.ncu.edu.tw/handle/987654321/109284

Title:	Some results on the target set selection problem
Authors:	葉鴻國;Chiang, Chun-Ying;Huang, Liang-Hao;Li, Bo-Jr;Wu, Jiaojiao;Yeh, Hong-Gwa
Contributors:	理學院數學系
Keywords:	Combinatorics;Convex and Discrete Geometry;Mathematical Modeling and Industrial Mathematics;Mathematics;Mathematics and Statistics;Operations Research/Decision Theory;Optimization;Theory of Computation
Date:	2013-05-01
Issue Date:	2026-04-23 16:22:48 (UTC+8)
Publisher:	Springer Netherlands;Boston: Springer US
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 ). 其他題名： 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
Appears in Collections:	[Department of Mathematics] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	12	View/Open

社群 sharing

Loading...