Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, September 25, 2007, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Rico Zenklusen
In the classical s-t network reliability problem a fixed network G is given including two designated vertices s and t (called terminals). The edges are subject to independent random failure, and the task is to compute the probability that s and t a re connected in the resulting network, which is known to be #P-complete. In this talk, I will discuss the issue of approximating the s-t reliability in case of a directed acyclic original network G. A specialized version of a Monte-Carlo algorithm given by Karp and Luby will be introduced and analyzed. For the case of uniform edge failure probabilities, I will present a worst-case bound on the number of samples that have to be drawn to obtain an epsilon-delta approximation, being sharper than the original upper bound. Computational results on two types of random networks (directed acyclic Delaunay graphs and a slightly modified version of a classical random graph) with up to one million vertices are presented. These results show the advantage of the introduced Monte-Carlo approach compared to direct simulation when small reliabilities have to be estimated and demonstrate its applicability on large-scale instances. Furthermore, applications to spreading processes on networks will be highlighted.
Joint work with Marco Laumanns.
Automatic MiSe System Software Version 1.4803M | admin login