Fast Sequential Importance Sampling to Estimate the Graph Reliability Polynomial
David G. Harris, Francis Sullivan, Isabel M. Beichl
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.
, Sullivan, F.
and Beichl, I.
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 1, 2023)