Push is Fast on Sparse Random Graphs
Push is Fast on Sparse Random Graphs
We consider the classical push broadcast process on a large class of sparse random multigraphs that includes random power law graphs and multigraphs. Our analysis shows that for every $\varepsilon>0$, with high probability (w.h.p.) $O(\log n)$ rounds are sufficient to inform all but an $\varepsilon$-fraction of the vertices (with high …