dc.creator | Rapaport Zimermann, Iván | |
dc.creator | Suchan, K. | |
dc.creator | Verstraete, J. | |
dc.creator | Todinca, I. | |
dc.date.accessioned | 2011-12-02T18:12:05Z | |
dc.date.available | 2011-12-02T18:12:05Z | |
dc.date.created | 2011-12-02T18:12:05Z | |
dc.date.issued | 2011-01 | |
dc.identifier | ALGORITHMICA Volume: 59 Issue: 1 Pages: 16-34 Published: JAN 2011 | |
dc.identifier | 0178-4617 | |
dc.identifier | DOI: 10.1007/s00453-009-9309-0 | |
dc.identifier | https://repositorio.uchile.cl/handle/2250/125556 | |
dc.description.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. | |
dc.language | en | |
dc.publisher | Springer | |
dc.subject | Bootstrap percolation | |
dc.title | On Dissemination Thresholds in Regular and Irregular Graph Classes | |
dc.type | Artículo de revista | |