Skip to Main content Skip to Navigation
Journal articles

Dynamic monopolies for interval graphs with bounded thresholds

Stéphane Bessy 1 Stefan Ehard 2 Lucia D. Penso 2 Dieter Rautenbach 2 
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : For a graph G and an integer-valued threshold function τ on its vertex set, a dynamic monopoly is a set of vertices of G such that iteratively adding to it vertices u of G that have at least τ (u) neighbors in it eventually yields the vertex set of G. We show that the problem of finding a dynamic monopoly of minimum order can be solved in polynomial time for interval graphs with bounded threshold functions, but is NP-hard for chordal graphs allowing unbounded threshold functions.
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Isabelle Gouat Connect in order to contact the contributor
Submitted on : Thursday, September 24, 2020 - 9:28:25 AM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM
Long-term archiving on: : Thursday, December 3, 2020 - 4:33:13 PM


Files produced by the author(s)




Stéphane Bessy, Stefan Ehard, Lucia D. Penso, Dieter Rautenbach. Dynamic monopolies for interval graphs with bounded thresholds. Discrete Applied Mathematics, Elsevier, 2019, 260, pp.256-261. ⟨10.1016/j.dam.2019.01.022⟩. ⟨lirmm-02947680⟩



Record views


Files downloads