Campus Event Calendar
Event Entry
New for: D3
What and Who
Rumor Spreading and Graph Conductance
George Giakkoupis
CNRS Paris
Talk
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 24 February 2011
14:00
30 Minutes
E1 4
TBD
Saarbrücken
Abstract
We study the connection between the rate at which a rumor spreads
throughout a graph and the conductance of the graph---a standard measure
of a graph's expansion properties.
We show that for any n-node graph with conductance phi, the classical
PUSH-PULL algorithm distributes a rumor to all nodes of the graph in
O((1/phi)log n) rounds with high probability.
This bound is tight in the sense that there exist graphs where at least
that many rounds are needed.
Contact
Thomas Sauerwald
--email hidden
passcode not visible
logged in users only
Thomas Sauerwald, 02/17/2011 00:53
Thomas Sauerwald, 02/11/2011 07:17
Thomas Sauerwald, 02/09/2011 18:30 -- Created document.
Thomas Sauerwald, 02/11/2011 07:17
Thomas Sauerwald, 02/09/2011 18:30 -- Created document.