toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Record Links
Author Rapaport, I.; Suchan, K.; Todinca, I.; Verstraete, J. pdf  doi
openurl 
  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 UAI @ eduardo.moreno @ Serial (down) 119  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: