Tight analysis of randomized rumor spreading in complete graphs

DOI10.1137/1.9781611973204.8MaRDI QIDQ5194760zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Marvin Künnemann

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

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

Recommendations

• Quasirandom rumor spreading on the complete graph is as fast as randomized rumor spreading
• Randomized rumor spreading revisited
• Asymptotics for push on the complete graph
• Randomized rumour spreading: the effect of the network topology
• Asymptotics for pull on the complete graph

Cited in

(14)

• Island models meet rumor spreading
• Broadcasting on paths and cycles
• Total flooding time and rumor propagation on graphs
• On broadcasting time in the model of travelling agents
• Asymptotics for pull on the complete graph
• On Spreading a Rumor
• Robustness of randomized rumour spreading
• scientific article; zbMATH DE number 7525473 (Why is no real title available?)
• Randomized rumor spreading revisited
• Randomized Rumor Spreading in Dynamic Graphs
• scientific article; zbMATH DE number 6783408 (Why is no real title available?)
• Asymptotics for push on the complete graph
• Asymptotics for push on the complete graph
• On the mean absorption time of multiple coalescing particles with removal at previously visited vertices

This page was built for publication: Tight analysis of randomized rumor spreading in complete graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5194760)