Name
Abstract | ||
|---|---|---|
We study the relation between the vertex expansion of a graph and the performance of randomized rumor spreading (push model). We prove that randomized rumor spreading takes O((1/α) · polylog(n)) time on any regular n-vertex graph with vertex expansion α. This bound extends previously known upper bounds by replacing conductance by vertex expansion. Our result is almost tight in the sense that the dependency on (1/α) is optimal (up to logarithmic factors) and that on non-regular graphs with constant vertex expansion, the runtime can be polynomial in n. Our upper bound also implies that randomized rumor spreading is "fast" on every vertex-transitive graph and yields a new upper bound on the cover time of random walks. We also exhibit a subtle difference between the impact of vertex expansion and conductance on rumor spreading. We show that there are regular graphs with constant vertex expansion for which randomized rumor spreading takes considerably longer than on any regular graph with constant conductance. Finally, we also prove a more general, but weaker result for the push & pull model which also covers non-regular graphs. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.5555/2133036.2133073 | SODA |
Keywords | Field | DocType |
regular n-vertex graph,non-regular graph,constant vertex expansion,regular graph,cover time,constant conductance,upper bound,randomized rumor,vertex expansion,vertex-transitive graph,random walk,randomized algorithms,leader election,distributed computing | Random regular graph,Discrete mathematics,Combinatorics,Circulant graph,Strongly regular graph,Vertex (graph theory),Cycle graph,Neighbourhood (graph theory),Regular graph,Mathematics,Feedback vertex set | Conference |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 23 | 1.03 |
References | Authors | |
20 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Sauerwald | 1 | 575 | 39.99 |
| Alexandre O. Stauffer | 2 | 130 | 11.34 |