Randomized Rumour Spreading: The Effect of the Network Topology

DOI10.1017/S0963548314000194zbMath1371.05289DBLPjournals/cpc/PanagiotouPS015OpenAlexW1992403724WikidataQ57991430 ScholiaQ57991430MaRDI QIDQ5364236

Xavier Pérez-Giménez, Thomas Sauerwald, He Sun, Konstantinos D. Panagiotou

Publication date: 4 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548314000194

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Stochastic analysis of rumor spreading with multiple pull operations ⋮ Asynchronous rumor spreading on random graphs ⋮ Continuous-time stochastic analysis of rumor spreading with multiple operations ⋮ Probabilistic Analysis of Rumor-Spreading Time ⋮ Propagation time for probabilistic zero forcing ⋮ Unnamed Item ⋮ Asymptotics for push on the complete graph ⋮ Randomized rumor spreading in poorly connected small-world networks ⋮ Robustness of randomized rumour spreading

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the runtime and robustness of randomized broadcasting
• The shortest-path problem for graphs with random arc-lengths
• Explicit construction of linear sized tolerant networks
• The eigenvalues of random symmetric matrices
• Almost tight bounds for rumour spreading with conductance
• Quasirandom Load Balancing
• Randomized broadcast in networks
• The cover time of sparse random graphs
• Expander graphs and their applications
• Rumor Spreading on Random Regular Graphs and Expanders
• Fast Distributed Algorithms for Computing Separable Functions
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Cover Time and Broadcast Time
• Probability and Computing
• Concentration of Measure for the Analysis of Randomized Algorithms
• Spectral norm of random matrices

This page was built for publication: Randomized Rumour Spreading: The Effect of the Network Topology