NIST logo

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

NIST Authors in Bold

Author(s): David G. Harris; Francis Sullivan; Isabel M. Beichl;
Title: Fast Sequential Importance Sampling fo Estimate the Graph Reliability Polynomial
Published: November 05, 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
Keywords: reliability polynomial; graph; fpras; network reliability; sequential importance sampling.
Research Areas: Modeling, Software, Statistics, Information Technology