Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree

DOI10.46298/dmtcs.6844zbMath1519.90249arXiv2007.03959OpenAlexW3041117735MaRDI 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

zbMATH Keywords

target setnon-monotone activation process

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (05C99)

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

This page was built for publication: Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree