NIST logo

Publication Citation: Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial

NIST Authors in Bold

Author(s): David G. Harris; Francis Sullivan; Isabel M. Beichl;
Title: Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial
Published: November 08, 2012
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
Pages: pp. 916 - 939
Keywords: reliability polynomial, graph, fpras, network reliability, sequential importance sampling.
Research Areas: Modeling, Software, Statistics, Information Technology
DOI: http://dx.doi.org/10.1007/s00453-012-9703-x  (Note: May link to a non-U.S. Government webpage)
PDF version: PDF Document Click here to retrieve PDF version of paper (808KB)