Treewidth governs the complexity of target set selection
From MaRDI portal
Publication:456700
DOI10.1016/J.DISOPT.2010.09.007zbMATH Open1248.90068OpenAlexW2148732839MaRDI QIDQ456700FDOQ456700
Authors: Oren Ben-Zwi, Daniel Lokshtanov, Ilan Newman, Danny Hermelin 
Publication date: 16 October 2012
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2010.09.007
Recommendations
- Latency-bounded target set selection in social networks
- Solving target set selection with bounded thresholds faster than \(2^n\)
- Solving target set selection with bounded thresholds faster than \(2^n\)
- Latency-bounded target set selection in social networks
- Target set selection parameterized by clique-width and maximum threshold
social networkstarget set selectionviral marketinggame of lifebounded tree-width algorithmbounded tree-width lower-bound
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Local majorities, coalitions and monopolies in graphs: A review
- Relationships between nondeterministic and deterministic tape complexities
- Complexity of Finding Embeddings in a k-Tree
- Title not available (Why is that?)
- Automata, Languages and Programming
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Title not available (Why is that?)
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the parameterized complexity of multiple-interval graph problems
- Size bounds for dynamic monopolies
- Title not available (Why is that?)
- Contagion
- Tight lower bounds for certain parameterized NP-hard problems
- Title not available (Why is that?)
- Dynamic monopolies of constant size
- On treewidth approximations.
Cited In (59)
- On the complexity of target set selection in simple geometric networks
- Immunization in the threshold model: a parameterized complexity study
- Parameterized complexity of weighted target set selection
- Graph burning in community-based networks
- Groups burning: analyzing spreading processes in community-based networks
- Minimal zero forcing sets
- On Structural Parameterizations of the Harmless Set Problem
- Target set selection with maximum activation time
- A parameterized complexity view on collapsing \(k\)-cores
- Exact solutions for latency-bounded target set selection problem on some special families of graphs
- Grundy Distinguishes Treewidth from Pathwidth
- How to choose friends strategically
- Spread of influence in weighted networks under time and budget constraints
- On reconfigurability of target sets
- Target set selection for conservative populations
- Dynamic monopolies for interval graphs with bounded thresholds
- On tractable cases of target set selection
- Constant thresholds can make target set selection tractable
- Improved Computational Approaches and Heuristics for Zero Forcing
- Title not available (Why is that?)
- On some tractable and hard instances for partial incentives and target set selection
- Whom to befriend to influence people
- Target set selection parameterized by clique-width and maximum threshold
- Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
- Active influence spreading in social networks
- Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree
- On irreversible spread of influence in edge-weighted graphs
- Parameterized approximability of maximizing the spread of influence in networks
- The \(t\)-latency bounded strong target set selection problem in some kinds of special family of graphs
- The complexity of finding harmless individuals in social networks
- Least cost influence propagation in (social) networks
- Optimizing spread of influence in social networks via partial incentives
- A fast and effective heuristic for discovering small target sets in social networks
- Evangelism in social networks
- Establishing herd immunity is hard even in simple geometric networks
- Influence diffusion in social networks under time window constraints
- Partial immunization of trees
- Some results on the target set selection problem
- On the harmless set problem parameterized by treewidth
- Parameterized complexity of immunization in the threshold model
- Computational approaches for zero forcing and related problems
- Latency-bounded target set selection in social networks
- Parameterizations of hitting set of bundles and inverse scope
- Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems
- Vaccinate your trees!
- Structure of graphs with locally restricted crossings
- Influence Diffusion in Social Networks under Time Window Constraints
- On the complexity of reasoning about opinion diffusion under majority dynamics
- On approximating target set selection
- Target set selection parameterized by vertex cover and more
- Weighted target set selection on trees and cycles
- Discovering small target sets in social networks: a fast and effective algorithm
- Latency-bounded target set selection in social networks
- The complexity of finding effectors
- Domination and convexity problems in the target set selection model
- Solving target set selection with bounded thresholds faster than \(2^n\)
- Solving target set selection with bounded thresholds faster than \(2^n\)
- Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis
- Target Set Selection in Dense Graph Classes
This page was built for publication: Treewidth governs the complexity of target set selection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456700)
