Linear Algebra and Sequential Importance Ssampling for Network Reliability

Published

December 11, 2011

Author(s)

David G. Harris, Francis Sullivan, Isabel M. Beichl

Abstract

The reliability polynomial of a graph gives the probability that a graph is connected as a function of the probability that each edge is connected. The coefficients of the reliability polynomial count the number of connected subgraphs of various sizes. Algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph's reliability polynomial. We develop a new bottom-up SIS algorithm for estimating the reliability polynomial by choosing a spanning tree and adding edges. This algorithm improves on existing bottom-up algorithms in that it has lower complexity O(E2V) as opposed to O(EV3), and it uses importance sampling to reduce variance.

Proceedings Title

Winter Simulation Conference

Conference Dates

December 11-14, 2011

Conference Location

Phoenix, AZ, US

Pub Type

Conferences

Download Paper

Local Download

Keywords

Monte Carlo methods, reliability, reliabilty polynomial, importance sampling

Citation

Harris, D. , Sullivan, F. and Beichl, I. (2011), Linear Algebra and Sequential Importance Ssampling for Network Reliability, Winter Simulation Conference, Phoenix, AZ, US, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=909109 (Accessed October 11, 2025)