Original paper
Rumor spreading and vertex expansion on regular graphs
Pages: 462 - 475
Published: Jan 23, 2011
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...
Paper Details
Title
Rumor spreading and vertex expansion on regular graphs
Published Date
Jan 23, 2011
Pages
462 - 475
Citation AnalysisPro
You’ll need to upgrade your plan to Pro
Looking to understand the true influence of a researcher’s work across journals & affiliations?
- Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
- Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.
Notes
History