Irreversible conversion processes with deadlines

详细信息    查看全文

• 作者：Dieter Rautenbach^a ; ^{dieter.rautenbach@uni-ulm.de" class="auth_mail} ; Viní ; cius Fernandes dos Santos^b ; ^{vinicius.santos@gmail.com" class="auth_mail} ; Philipp M. Schä ; fer^a ; ^{philipp.schaefer@gmail.com" class="auth_mail}
• 关键词：Iterative graph process ; Dynamic monopoly ; Domination ; Independence
• 刊名：Journal of Discrete Algorithms
• 出版年：May 2014
• 年：2014
• 卷：26
• 期：Complete
• 页码：69-76
• 全文大小：233 K

文摘

Given a graph G  , a deadline t_d(u)$t_d(u)$ and a time-dependent threshold f(u,t)$f(u,t)$ for every vertex u   of G  , we study sequences C=(c₀,c₁,…)$\mathcal{C}=(c_0,c_1,\dots )$ of 0/1-labelings c_i$c_i$ of the vertices of G   such that for every t∈N$t\in \mathbb{N}$, we have c_t(u)=1$c_t(u)=1$ if and only if either c_t−1(u)=1$c_{t-1}(u)=1$ or at least f(u,t−1)$f(u,t-1)$ neighbors v   of u   satisfy c_t−1(v)=1$c_{t-1}(v)=1$. The sequence C$\mathcal{C}$ models the spreading of a property/commodity within a network and it is said to converge to 1 on time, if c_td(u)(u)=1$c_{t_d(u)}(u)=1$ for every vertex u   of G  , that is, if every vertex u   has the spreading property/received the spreading good by time t_d(u)$t_d(u)$.

We study the smallest number irr(G,t_d,f)$\mathit{irr}(G,t_d,f)$ of vertices u   with initial label c₀(u)$c_0(u)$ equal to 1 that result in a sequence C$\mathcal{C}$ converging to 1 on time. If G   is a forest or a clique, we present efficient algorithms computing irr(G,t_d,f)$\mathit{irr}(G,t_d,f)$. Furthermore, we prove lower and upper bounds relying on counting and probabilistic arguments. For special choices of t_d$t_d$ and f  , the parameter irr(G,t_d,f)$\mathit{irr}(G,t_d,f)$ coincides with well-known graph parameters related to domination and independence in graphs.