Combinatorial model and bounds for target set selection

DOI10.1016/j.tcs.2010.08.021zbMath1235.90168OpenAlexW2097938283MaRDI QIDQ410735

Oren Ben-Zwi, Eyal Ackerman, Guy Wolfovitz

Publication date: 3 April 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.021

zbMATH Keywords

target set selection monotone irreversible dynamic monopoly (dynamo)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Related Items

Complexity of equilibrium in competitive diffusion games on social networks ⋮ Computational approaches for zero forcing and related problems ⋮ Discovering small target sets in social networks: a fast and effective algorithm ⋮ Vaccinate your trees! ⋮ Target Set Selection in Dense Graph Classes ⋮ Optimizing Spread of Influence in Social Networks via Partial Incentives ⋮ Least cost influence propagation in (social) networks ⋮ A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks ⋮ Generalized threshold processes on graphs ⋮ ON DYNAMIC MONOPOLIES OF GRAPHS WITH PROBABILISTIC THRESHOLDS ⋮ Improved Computational Approaches and Heuristics for Zero Forcing ⋮ Fortification Against Cascade Propagation Under Uncertainty ⋮ Contagious sets in dense graphs ⋮ Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems ⋮ Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree ⋮ On non-progressive spread of influence through social networks ⋮ Immune sets in monotone infection rules. Characterization and complexity ⋮ New computational approaches for the power dominating set problem: Set covering and the neighborhoods of zero forcing forts ⋮ Weighted target set selection on trees and cycles ⋮ Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives ⋮ Groups burning: analyzing spreading processes in community-based networks ⋮ New ordering methods to construct contagious sets and induced degenerate subgraphs ⋮ Target set selection with maximum activation time ⋮ Solving target set selection with bounded thresholds faster than $2^n$ ⋮ Target set selection on generalized pancake graphs ⋮ New bounds for contagious sets ⋮ Target set selection in social networks with tiered influence and activation thresholds ⋮ Dynamic monopolies and feedback vertex sets in hexagonal grids ⋮ Triggering cascades on undirected connected graphs ⋮ Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids ⋮ On reversible cascades in scale-free and Erdős-Rényi random graphs ⋮ On dynamic monopolies of graphs: the average and strict majority thresholds ⋮ Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs ⋮ Latency-bounded target set selection in social networks ⋮ Dynamic monopolies with randomized starting configuration ⋮ Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks ⋮ Active influence spreading in social networks ⋮ Optimizing spread dynamics on graphs by message passing ⋮ Target set selection for conservative populations ⋮ Triggering cascades on strongly connected directed graphs ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees ⋮ Integer programming approach to static monopolies in graphs ⋮ 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 ⋮ A polyhedral study of dynamic monopolies ⋮ Facets of the dynamic monopoly polytope: linear ordering formulation ⋮ Whom to befriend to influence people ⋮ An exact algorithm for robust influence maximization ⋮ On giant components and treewidth in the layers model ⋮ Fast and frugal targeting with incentives ⋮ Partial immunization of trees ⋮ Evangelism in Social Networks ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ 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 irreversible spread of influence in edge-weighted graphs ⋮ Minimal contagious sets in random regular graphs ⋮ On reconfigurability of target sets ⋮ A polyhedral approach to least cost influence maximization in social networks ⋮ On the complexity of the vector connectivity problem ⋮ An inclusion hierarchy of irreversible dynamos ⋮ Exact solutions for latency-bounded target set selection problem on some special families of graphs

Cites Work