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 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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02947680
Contributor : Isabelle Gouat <>
Submitted on : Thursday, September 24, 2020 - 9:28:25 AM
Last modification on : Friday, September 25, 2020 - 3:28:09 AM
Long-term archiving on: : Thursday, December 3, 2020 - 4:33:13 PM

File

1802.03935.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Stéphane Bessy, Stefan Ehard, Lucia 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⟩

Share

Metrics

Record views

55

Files downloads

25