NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.

Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.

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.

PUBLICATIONS

Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial

Published

Author(s)

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

Abstract

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.
Citation
Algorithmica
Pub Type
Journals

Download Paper

https://doi.org/10.1007/s00453-012-9703-x
Local Download

Keywords

reliability polynomial, graph, fpras, network reliability, sequential importance sampling.
Statistical analysis, Numerical methods and software, Modeling and simulation research and Information technology

Citation

Harris, D. , Sullivan, F. and Beichl, I. (2012), Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial, Algorithmica, [online], https://doi.org/10.1007/s00453-012-9703-x, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=905927 (Accessed October 16, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created November 7, 2012, Updated October 12, 2021
Was this page helpful?