|
|
 |
 |
Monte-Carlo Estimation of s-t Reliability in Acyclic Networks
Marco Laumanns
ASU
|
Monte-Carlo Estimation of s-t Reliability in Acyclic Networks Marco Laumanns ASU |
|
ABSTRACT In the classical s-t network reliability model we have a fixed network G=(V,E) with two special vertices s and t (called terminals) and whose edges are subject to independent random failure. We are interested in estimating the probability that s and t are connected in the resulting network in the case of an acyclic original network, which is relevant for certain disease spreading models especially when the failure probabilies are high. We introduce and analyze an adapted version of the Monte-Carlo algorithm by Karp and Luby and give a worst-case bound on the number of samples that have to be drawn to get an epsilon-delta approximation in the case of uniform edge failure probability. Computational results show that the approach works well in practice and is applicable on large-scale instances. |