Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree
From MaRDI portal
Publication:6045404
DOI10.46298/dmtcs.6844zbMath1519.90249arXiv2007.03959MaRDI QIDQ6045404
Dieter Rautenbach, Julien Baste, Stefan Ehard
Publication date: 30 May 2023
Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.03959
90C35: Programming involving graphs or networks
05C10: Planar graphs; geometric and topological aspects of graph theory
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C99: Graph theory
Cites Work
- Unnamed Item
- Unnamed Item
- Combinatorial model and bounds for target set selection
- Treewidth governs the complexity of target set selection
- Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
- Irreversible conversion of graphs
- Reversible iterative graph processes
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- Size bounds for dynamic monopolies
- Treewidth. Computations and approximations
- Dynamic monopolies for interval graphs with bounded thresholds
- On some tractable and hard instances for partial incentives and target set selection
- Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- On the Approximability of Influence in Social Networks
- The Complexity of Multiterminal Cuts
