Dynamic monopolies for interval graphs with bounded thresholds - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2019

Dynamic monopolies for interval graphs with bounded thresholds

Résumé

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.
Fichier principal
Vignette du fichier
1802.03935.pdf (137.59 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-02947680 , version 1 (24-09-2020)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More