Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Linear Algebra and Sequential Importance Ssampling for Network Reliability



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


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


Monte Carlo methods, reliability, reliabilty polynomial, importance sampling


Harris, D. , Sullivan, F. and Beichl, I. (2011), Linear Algebra and Sequential Importance Ssampling for Network Reliability, Winter Simulation Conference, Phoenix, AZ, US, [online], (Accessed June 13, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created December 10, 2011, Updated October 12, 2021