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.

Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial



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


The reliability polynomial of a graph measures the number of its connected subgraphs of various sizes. Algortihms based on sequential importance sampling (SIS) have been proposed to estimate a graph's reliahbility polynomial. We develop an improved SIS algorithm for estimating the reliability polynomial. This algorithm is orders of magnitude faster than the previous algorithm, running in time O^(E) as opposed to O(E^2), where E is the number of edges in the graph. We analyse the variance of these algorithms from a theoretical point of view, including their worst-case behavior. In addition to the theoretical analysis, we discuss methods for estimating the variance and describe experimental results on a variety of random graphs.


reliability polynomial, graph, fpras, network reliability, sequential importance sampling.


Harris, D. , Sullivan, F. and Beichl, I. (2012), Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial, Algorithmica, [online],, (Accessed July 16, 2024)


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

Created November 7, 2012, Updated October 12, 2021