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

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

Keywords

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

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 March 28, 2024)
Created November 7, 2012, Updated October 12, 2021