Geodesic
Variants of Spreading Messages
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Fourth International Workshop on Algorithms and Computation (WALCOM 2010) , Tome 15 (2011) no. 5, pp. 683-699.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

In a distributed computing environment a faulty node could lead other nodes in the system to behave in a faulty manner. An initial set of faults could make all the nodes in the system become faulty. Such a set is called an irreversible dynamo. This is modelled as spreading a message among individuals V in a community G=( V,E) where E represents the acquaintance relation. A particular individual will believe a message if some of the individual's acquaintances believe the same and forward the believed messages to its neighbours. We are interested in finding the minimum set of initial individuals to be considered as convinced, called the min-seed, such that every individual in the community is finally convinced. In this paper we give an upper bound on the cardinality of the min-seed for undirected graphs. We consider some interesting variants of the problem and analyse their complexities and give some approximate algorithms.
DOI : 10.7155/jgaa.00244
Keywords: Vertex Cover, Bipartite Graphs, Approximate Algorithms, NP-complete 
@article{JGAA_2011_15_5_a5,
     author = {T V Thirumala Reddy and C Pandu Rangan},
     title = {Variants of {Spreading} {Messages}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {683--699},
     publisher = {mathdoc},
     volume = {15},
     number = {5},
     year = {2011},
     doi = {10.7155/jgaa.00244},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00244/}
}
TY  - JOUR
AU  - T V Thirumala Reddy
AU  - C Pandu Rangan
TI  - Variants of Spreading Messages
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 683
EP  - 699
VL  - 15
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00244/
DO  - 10.7155/jgaa.00244
LA  - en
ID  - JGAA_2011_15_5_a5
ER  - 
%0 Journal Article
%A T V Thirumala Reddy
%A C Pandu Rangan
%T Variants of Spreading Messages
%J Journal of Graph Algorithms and Applications
%D 2011
%P 683-699
%V 15
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00244/
%R 10.7155/jgaa.00244
%G en
%F JGAA_2011_15_5_a5
T V Thirumala Reddy; C Pandu Rangan. Variants of Spreading Messages. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Fourth International Workshop on Algorithms and Computation (WALCOM 2010)
					, Tome 15 (2011) no. 5, pp. 683-699. doi : 10.7155/jgaa.00244. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00244/

Cité par Sources :