Authors
Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi
Publication date
2010/1/17
Book
Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms
Pages
1657-1663
Publisher
Society for Industrial and Applied Mathematics
Description
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].
Total citations
2010201120122013201420152016201720182019202020212022202320246111510116121191146211
Scholar articles
F Chierichetti, S Lattanzi, A Panconesi - Proceedings of the twenty-first annual ACM-SIAM …, 2010