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]. Copyright © by SIAM.
Rumour spreading and graph conductance / Chierichetti, Flavio; SILVIO LATTANZI, And; Panconesi, Alessandro. - (2010), pp. 1657-1663. (Intervento presentato al convegno ACM-SIAM Symposium on Discrete Algorithms, (SODA 2010) tenutosi a Austin; United States nel January 17-19, 2010).
Rumour spreading and graph conductance.
CHIERICHETTI, FLAVIO;PANCONESI, Alessandro
2010
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]. Copyright © by SIAM.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
