Fast information spreading in graphs with large weak conductance

DOI10.1137/110845380MaRDI QIDQ4910571zbMATH OpenOpenAlexFDO

Authors Keren Censor-Hillel, Hadas Shachnai

Publication date 19 March 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

distributed computinginformation spreadingrandomized algorithmsweak conductance

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Distributed algorithms (68W15)

Recommendations

• Fast information spreading in graphs with large weak conductance
• Partial information spreading with application to distributed maximum coverage
• Rumour spreading and graph conductance
• Tight bounds for rumor spreading in graphs of a given conductance
• Almost tight bounds for rumour spreading with conductance

Cited in

(6)

• FAST INFORMATION PROPAGATION IN SOCIAL NETWORKS
• Partial information spreading with application to distributed maximum coverage
• Minimum Weight Dynamo and Fast Opinion Spreading
• Fast information spreading in graphs with large weak conductance
• Global computation in a poorly connected world
• Time- and communication-efficient overlay network construction via gossip

This page was built for publication: Fast information spreading in graphs with large weak conductance

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