On mixing and edge expansion properties in randomized broadcasting

DOI10.1007/s00453-008-9245-4zbMath1187.68702OpenAlexW2149345630MaRDI QIDQ848940

Thomas Sauerwald

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9245-4

zbMATH Keywords

Markov chainrandomized algorithmdistributed and parallel algorithm

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

Diameter and broadcast time of random geometric graphs in arbitrary dimensions ⋮ On the Push&Pull Protocol for Rumor Spreading ⋮ Breaking the \(\log n\) barrier on rumor spreading ⋮ Unnamed Item

Cites Work

• Adaptive broadcasting with faulty nodes
• Randomized broadcast in networks
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs
• On Spreading a Rumor
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Assignment of Numbers to Vertices
• On the Runtime and Robustness of Randomized Broadcasting
• Probability and Computing
• Efficient schemes for nearest neighbor load balancing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On mixing and edge expansion properties in randomized broadcasting