| Author | dc.contributor.author | Rapaport Zimermann, Iván | es_CL |
| Author | dc.contributor.author | Suchan, K. | es_CL |
| Author | dc.contributor.author | Todinca, I. | |
| Author | dc.contributor.author | Verstraete, J. | es_CL |
| Admission date | dc.date.accessioned | 2011-12-02T18:12:05Z | |
| Available date | dc.date.available | 2011-12-02T18:12:05Z | |
| Publication date | dc.date.issued | 2011-01 | |
| Cita de ítem | dc.identifier.citation | ALGORITHMICA Volume: 59 Issue: 1 Pages: 16-34 Published: JAN 2011 | es_CL |
| Identifier | dc.identifier.issn | 0178-4617 | |
| Identifier | dc.identifier.other | DOI: 10.1007/s00453-009-9309-0 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/125556 | |
| General note | dc.description | Artículo de publicación ISI | es_CL |
| Abstract | 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. | es_CL |
| Lenguage | dc.language.iso | en | es_CL |
| Publisher | dc.publisher | Springer | es_CL |
| Keywords | dc.subject | Bootstrap percolation | es_CL |
| Título | dc.title | On Dissemination Thresholds in Regular and Irregular Graph Classes | es_CL |
| Document type | dc.type | Artículo de revista | |
