Rumor spreading with bounded in-degree

DOI10.1016/j.tcs.2018.05.041zbMath1432.68017arXiv1506.00828OpenAlexW2809576649WikidataQ129626899 ScholiaQ129626899MaRDI QIDQ2292916

Yannic Maus, Sebastian Daum, Fabian Kuhn

Publication date: 6 February 2020

Published in: Theoretical Computer Science, Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.00828

zbMATH Keywords

gossipingcouplingstochastic dominancerumor spreadingpullpushrandom phone call model

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Network protocols (68M12)

Related Items (7)

Stochastic analysis of rumor spreading with multiple pull operations ⋮ ILSR rumor spreading model with degree in complex network ⋮ Continuous-time stochastic analysis of rumor spreading with multiple operations ⋮ Probabilistic Analysis of Rumor-Spreading Time ⋮ Unnamed Item ⋮ Rumor spreading with bounded in-degree ⋮ Robustness of randomized rumour spreading

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• The shortest-path problem for graphs with random arc-lengths
• Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
• Rumor spreading with bounded in-degree
• An efficient heuristic for broadcasting in networks
• On the Push&Pull Protocol for Rumour Spreading
• Almost tight bounds for rumour spreading with conductance
• Simple, Fast and Deterministic Gossip and Rumor Spreading
• Randomized broadcast in networks
• Fast Distributed Algorithms for Computing Separable Functions
• Fast Information Spreading in Graphs with Large Weak Conductance
• How Asynchrony Affects Rumor Spreading Time
• Tight Bounds for Rumor Spreading with Vertex Expansion
• Global computation in a poorly connected world
• The Random-Cluster Model
• The Existence of Probability Measures with Given Marginals

This page was built for publication: Rumor spreading with bounded in-degree