Campus Event Calendar

Event Entry

New for: D3

What and Who

Flooding and diameter in weighted random graphs

Hamed Amini
ENS Paris
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI  
AG Audience

Date, Time and Location

Friday, 13 August 2010
30 Minutes
E1 4


We study the impact of the edge weights on distances in

diluted random graphs. We interpret these weights as delays, and take
them as i.i.d. exponential random variables. We analyze the edge
flooding time defined as the minimum time needed to reach all nodes
from one uniformly chosen node, and the edge diameter corresponding to
the worst case edge flooding time. Under some regularity conditions on
the degree sequence of the random graph, we show that these quantities
grow as the logarithm of n, when the size of the graph n tends to
infinity. We also drive the exact value for the prefactors.

These results allow us to analyze a randomized broadcast algorithm in
continuous time for random regular graphs. Surprisingly, the
continuous time version of the algorithm performs better than its
synchronized version. We show that this counter-intuitive fact is due to the variability of the exponential.


Nikolaos Fountoulakis
--email hidden
passcode not visible
logged in users only

Nikolaos Fountoulakis, 07/30/2010 17:04 -- Created document.