Dynamic monopolies for interval graphs with bounded thresholds

DOI10.1016/j.dam.2019.01.022zbMath1409.05202arXiv1802.03935OpenAlexW2963725225WikidataQ128375117 ScholiaQ128375117MaRDI QIDQ1741518

Stefan Ehard, Stéphane Bessy, Dieter Rautenbach, Lucia Draque Penso

Publication date: 3 May 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.03935

zbMATH Keywords

interval graphtarget set selectiondynamic monopoly

Mathematics Subject Classification ID

Dynamic programming (90C39) Graph theory (05C99) Connectivity (05C40)

Related Items (5)

Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree ⋮ Establishing herd immunity is hard even in simple geometric networks ⋮ Target set selection with maximum activation time ⋮ On some tractable and hard instances for partial incentives and target set selection ⋮ On reconfigurability of target sets

Cites Work

• Unnamed Item
• Treewidth governs the complexity of target set selection
• Irreversible conversion of graphs
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Some results on the target set selection problem
• Constant thresholds can make target set selection tractable
• On the Approximability of Influence in Social Networks
• Irreversible 2-conversion set in graphs of bounded degree
• Target Set Selection Parameterized by Clique-Width and Maximum Threshold
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

This page was built for publication: Dynamic monopolies for interval graphs with bounded thresholds