 |
HAL-LIRMM - Open Archive |  |
Journal articles
Dynamic monopolies for interval graphs with bounded thresholds
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.
Cited literature [11 references]
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
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)