Take a sneak peek at the new NIST.gov and let us know what you think!
(Please note: some content may not be complete on the beta site.).
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.|
|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:||Click here to retrieve PDF version of paper (808KB)|