Abstract | ||
---|---|---|
For a graph G and a non-negative integer-valued 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 study the problem of maximizing the minimum order of a dynamic monopoly by increasing the threshold values of individual vertices subject to vertex-dependent lower and upper bounds, and fixing the total increase. We solve this problem efficiently for trees, which extends a result of Khoshkhah and Zaker (2015). |
Year | DOI | Venue |
---|---|---|
2020 | 10.1016/j.disopt.2020.100568 | Discrete Optimization |
Keywords | Field | DocType |
05C69,05C05 | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Monopoly,Mathematics | Journal |
Volume | ISSN | Citations |
35 | 1572-5286 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mitre Dourado | 1 | 90 | 18.43 |
Stefan Ehard | 2 | 1 | 2.39 |
Lucia Draque Penso | 3 | 196 | 20.46 |
Dieter Rautenbach | 4 | 946 | 138.87 |