Rumour Spreading and Graph Conductance
Lists
Only you see this
Abstract
We show that if a connected graph with n nodes has conductance ϕ then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within O(log4 n/ϕ6) many steps, with high probability, using the PUSH-PULL strategy. An interesting feature of our approach is that it draws a connection between rumour spreading and the spectral sparsification procedure of Spielman and Teng [23].
BibTeX
@inproceedings{chierichetti2010rumour,
author = {Flavio Chierichetti and Silvio Lattanzi and Alessandro Panconesi},
title = {{Rumour Spreading and Graph Conductance}},
booktitle = {SODA},
year = {2010},
doi = {10.1137/1.9781611973075.135},
}Loading related content...