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 December 14, 2024)
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,
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
Keywords
reliability polynomial, graph, fpras, network reliability, sequential importance sampling.
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.
Created November 7, 2012, Updated October 12, 2021