Treewidth governs the complexity of target set selection
From MaRDI portal
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
Cites work
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- scientific article; zbMATH DE number 5485445 (Why is no real title available?)
- scientific article; zbMATH DE number 5764908 (Why is no real title available?)
- scientific article; zbMATH DE number 1301101 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Automata, Languages and Programming
- Complexity of Finding Embeddings in a k-Tree
- Contagion
- Dynamic monopolies of constant size
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Graph minors. II. Algorithmic aspects of tree-width
- Local majorities, coalitions and monopolies in graphs: A review
- On the parameterized complexity of multiple-interval graph problems
- On treewidth approximations.
- Relationships between nondeterministic and deterministic tape complexities
- Size bounds for dynamic monopolies
- Tight lower bounds for certain parameterized NP-hard problems
Cited in
(57)- Groups burning: analyzing spreading processes in community-based networks
- Minimal zero forcing sets
- On Structural Parameterizations of the Harmless Set Problem
- On the complexity of target set selection in simple geometric networks
- Target set selection with maximum activation time
- Parameterized complexity of weighted target set selection
- Graph burning in community-based networks
- Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems
- Partial immunization of trees
- Target Set Selection in Dense Graph Classes
- The complexity of finding harmless individuals in social networks
- Target set selection parameterized by vertex cover and more
- Improved Computational Approaches and Heuristics for Zero Forcing
- Some results on the target set selection problem
- On irreversible spread of influence in edge-weighted graphs
- Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree
- Vaccinate your trees!
- Computational approaches for zero forcing and related problems
- Least cost influence propagation in (social) networks
- On the complexity of reasoning about opinion diffusion under majority dynamics
- Weighted target set selection on trees and cycles
- A parameterized complexity view on collapsing \(k\)-cores
- Spread of influence in weighted networks under time and budget constraints
- How to choose friends strategically
- On the harmless set problem parameterized by treewidth
- Parameterized complexity of immunization in the threshold model
- Influence Diffusion in Social Networks under Time Window Constraints
- On reconfigurability of target sets
- The \(t\)-latency bounded strong target set selection problem in some kinds of special family of graphs
- Establishing herd immunity is hard even in simple geometric networks
- On approximating target set selection
- Target set selection for conservative populations
- Discovering small target sets in social networks: a fast and effective algorithm
- Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
- Target set selection parameterized by clique-width and maximum threshold
- Optimizing spread of influence in social networks via partial incentives
- A fast and effective heuristic for discovering small target sets in social networks
- Latency-bounded target set selection in social networks
- Parameterized approximability of maximizing the spread of influence in networks
- Latency-bounded target set selection in social networks
- Evangelism in social networks
- Parameterizations of hitting set of bundles and inverse scope
- Exact solutions for latency-bounded target set selection problem on some special families of graphs
- Structure of graphs with locally restricted crossings
- Dynamic monopolies for interval graphs with bounded thresholds
- On tractable cases of target set selection
- Domination and convexity problems in the target set selection model
- Solving target set selection with bounded thresholds faster than \(2^n\)
- Grundy distinguishes treewidth from pathwidth
- On some tractable and hard instances for partial incentives and target set selection
- Solving target set selection with bounded thresholds faster than \(2^n\)
- Active influence spreading in social networks
- Influence diffusion in social networks under time window constraints
- Constant thresholds can make target set selection tractable
- Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis
- Immunization in the threshold model: a parameterized complexity study
- Grundy Distinguishes Treewidth from Pathwidth
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)
