کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433847 | 689640 | 2015 | 8 صفحه PDF | دانلود رایگان |
Consider the following process of activation on a strongly connected directed graph G(V,E)G(V,E) with threshold function ϕ:V→Nϕ:V→N. In round zero, a set of vertices, called the seeds, are active. Thereafter, a vertex v∈Vv∈V is activated in a round if it has at least ϕ(v)ϕ(v) active in-neighbors in the previous round. Once a vertex is activated, it remains active. Sets of seeds activating all vertices after a finite number of rounds are known in the literature as irreversible dynamic monopolies (a.k.a. perfect target sets) corresponding to (G,ϕ)(G,ϕ). With ϕ(v)=⌈ρdeg−(v)⌉ for all v∈Vv∈V, where deg−(v)deg−(v) denotes the indegree of v and ρ∈(0,1], this paper proves the existence of an irreversible dynamic monopoly of size no more than max{4.92ρ|V|,1}.
Journal: Theoretical Computer Science - Volume 593, 16 August 2015, Pages 62–69