|   | 
Details
   web
Record
Author Rapaport, I.; Suchan, K.; Todinca, I.; Verstraete, J.
Title On Dissemination Thresholds in Regular and Irregular Graph Classes Type
Year 2011 Publication Algorithmica Abbreviated Journal Algorithmica
Volume 59 Issue 1 Pages 16-34
Keywords Bootstrap percolation; Cubic graphs; Information dissemination
Abstract We investigate the natural situation of the dissemination of information on various graph classes starting with a random set of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high probability, the information will not spread to all vertices in the graph if p < 1/2. We give families of graphs in which information spreads to all vertices with high probability for relatively small values of p.
Address [Todinca, I.] Univ Orleans, LIFO, Orleans, France, Email: rapaport@dim.uchile.cl
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0178-4617 ISBN Medium
Area Expedition Conference
Notes WOS:000286525300003 Approved
Call Number (up) UAI @ eduardo.moreno @ Serial 119
Permanent link to this record