Name
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. It is known that the problem of finding a dynamic monopoly of minimum order is NP-hard for split graphs. We show that this problem can be solved in polynomial time for interval graphs with bounded threshold functions. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.dam.2019.01.022 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Dynamic monopoly,Target set selection,Interval graph | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Chordal graph,Monopoly,Time complexity,Mathematics,Threshold function,Bounded function | Journal |
Volume | ISSN | Citations |
260 | 0166-218X | 1 |
PageRank | References | Authors |
0.36 | 11 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Stefan Ehard | 2 | 1 | 2.39 |
| Lucia Draque Penso | 3 | 196 | 20.46 |
| Dieter Rautenbach | 4 | 946 | 138.87 |