| |
Record |
Links |
|
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 |
