کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431301 | 688499 | 2014 | 8 صفحه PDF | دانلود رایگان |
Given a graph G , a deadline td(u)td(u) and a time-dependent threshold f(u,t)f(u,t) for every vertex u of G , we study sequences C=(c0,c1,…)C=(c0,c1,…) of 0/1-labelings cici of the vertices of G such that for every t∈Nt∈N, we have ct(u)=1ct(u)=1 if and only if either ct−1(u)=1ct−1(u)=1 or at least f(u,t−1)f(u,t−1) neighbors v of u satisfy ct−1(v)=1ct−1(v)=1. The sequence CC models the spreading of a property/commodity within a network and it is said to converge to 1 on time, if ctd(u)(u)=1ctd(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 td(u)td(u).We study the smallest number irr(G,td,f)irr(G,td,f) of vertices u with initial label c0(u)c0(u) equal to 1 that result in a sequence CC converging to 1 on time. If G is a forest or a clique, we present efficient algorithms computing irr(G,td,f)irr(G,td,f). Furthermore, we prove lower and upper bounds relying on counting and probabilistic arguments. For special choices of tdtd and f , the parameter irr(G,td,f)irr(G,td,f) coincides with well-known graph parameters related to domination and independence in graphs.
Journal: Journal of Discrete Algorithms - Volume 26, May 2014, Pages 69–76