Estimation of Small s-t Reliabilities in Acyclic Networks

Details Estimation of Small s-t Reliabilities in Acyclic Networks Estimation of Small s-t Reliabilities in Acyclic Networks

2007-07-21

arxiv.org/abs/0707.3231v1

Computer Science

Discrete Mathematics

Scientific paper

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 are connected in the resulting network, which is known to be #P-complete. In this paper we are interested in approximating the s-t reliability in case of a directed acyclic original network G. We introduce and analyze a specialized version of the Monte-Carlo algorithm given by Karp and Luby. For the case of uniform edge failure probabilities, we give 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. We also derive a variance reduction of the estimator which reduces the expected number of iterations to perform to achieve the desired accuracy when applied in conjunction with different stopping rules. Initial 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.

Affiliated with

Also associated with

No associations

Rating

Estimation of Small s-t Reliabilities in Acyclic Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Estimation of Small s-t Reliabilities in Acyclic Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Estimation of Small s-t Reliabilities in Acyclic Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-433916