| 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 |
UAI @ eduardo.moreno @ |
Serial |
119 |
| Permanent link to this record |
