Some results on the target set selection problem

DOI10.1007/s10878-012-9518-3zbMath1273.90224arXiv1111.6685OpenAlexW2062667824MaRDI QIDQ1956258

Jiaojiao Wu, Liang-Hao Huang, Bo-Jr Li, Chun-Ying Chiang, Hong-Gwa Yeh

Publication date: 13 June 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1111.6685

zbMATH Keywords

treeHamming graphsocial networkschordal graphblock graphtarget set selectionviral marketingdiffusion of innovationsdynamic monopolyirreversible spread of influenceblock-cactus graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (33)

Computational approaches for zero forcing and related problems ⋮ A global optimization algorithm for target set selection problems ⋮ Discovering small target sets in social networks: a fast and effective algorithm ⋮ Vaccinate your trees! ⋮ Diffusion centrality: a paradigm to maximize spread in social networks ⋮ Target Set Selection in Dense Graph Classes ⋮ Optimizing Spread of Influence in Social Networks via Partial Incentives ⋮ On the harmless set problem parameterized by treewidth ⋮ A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks ⋮ ON DYNAMIC MONOPOLIES OF GRAPHS WITH PROBABILISTIC THRESHOLDS ⋮ Improved Computational Approaches and Heuristics for Zero Forcing ⋮ Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ Weighted target set selection on trees and cycles ⋮ Target set selection with maximum activation time ⋮ Target set selection on generalized pancake graphs ⋮ Latency-bounded target set selection in social networks ⋮ Dynamic monopolies for interval graphs with bounded thresholds ⋮ Constant thresholds can make target set selection tractable ⋮ On some tractable and hard instances for partial incentives and target set selection ⋮ The \(t\)-latency bounded strong target set selection problem in some kinds of special family of graphs ⋮ Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis ⋮ Whom to befriend to influence people ⋮ Fast and frugal targeting with incentives ⋮ Partial immunization of trees ⋮ Evangelism in Social Networks ⋮ Target set selection parameterized by vertex cover and more ⋮ The complexity of finding harmless individuals in social networks ⋮ Influence diffusion in social networks under time window constraints ⋮ Spread of influence in weighted networks under time and budget constraints ⋮ Influence Diffusion in Social Networks under Time Window Constraints ⋮ On reconfigurability of target sets ⋮ Exact solutions for latency-bounded target set selection problem on some special families of graphs

Cites Work

• Unnamed Item
• Treewidth governs the complexity of target set selection
• On rigid circuit graphs
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Dynamic monopolies in tori.
• Local majorities, coalitions and monopolies in graphs: A review
• Incidence matrices and interval graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• On the Approximability of Influence in Social Networks
• Algorithmic Aspects of Vertex Elimination on Graphs

This page was built for publication: Some results on the target set selection problem