Tight Analysis of Randomized Rumor Spreading in Complete Graphs

DOI10.1137/1.9781611973204.8zbMath1430.68193OpenAlexW1569012753MaRDI QIDQ5194760

Marvin Künnemann, Benjamin Doerr

Publication date: 17 September 2019

Published in: 2014 Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973204.8

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Random walks on graphs (05C81)

Related Items (8)

Broadcasting on paths and cycles ⋮ On broadcasting time in the model of travelling agents ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Asymptotics for pull on the complete graph ⋮ Island models meet rumor spreading ⋮ Unnamed Item ⋮ Asymptotics for push on the complete graph ⋮ Robustness of randomized rumour spreading

This page was built for publication: Tight Analysis of Randomized Rumor Spreading in Complete Graphs