Campus Event Calendar
Event Entry
What and Who
Rumor Spreading and Vertex Expansion
Thomas Sauerwald
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 3 December 2010
13:00
30 Minutes
Warning: Date has changed!
E1 4
024
Saarbrücken
Abstract
We study the relation between the vertex expansion of a graph and the performance of randomized rumor spreading (push model). We prove that randomized rumor spreading takes O( (1/alpha) * polylog(n) ) time on any regular n-vertex graph with vertex expansion alpha. This bound improves on previously known upper bounds by essentially replacing the conductance of the graph by its vertex expansion.
(joint work with Alexandre Stauffer)
Contact
Thomas Sauerwald
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Randomized Algorithms; Distributed Computing
Thomas Sauerwald, 11/18/2010 11:38
Thomas Sauerwald, 11/16/2010 22:37 -- Created document.
Thomas Sauerwald, 11/16/2010 22:37 -- Created document.