Harris, D.
, Sullivan, F.
and Beichl, I.
(2011),
Linear Algebra and Sequential Importance Ssampling for Network Reliability, Winter Simulation Conference, Phoenix, AZ, US, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=909109
(Accessed April 19, 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.
Linear Algebra and Sequential Importance Ssampling for Network Reliability
Published
Author(s)
David G. Harris, Francis Sullivan,
Abstract
The reliability polynomial of a graph gives the probability that a graph is connected as a function of the probability that each edge is connected. The coefficients of the reliability polynomial count the number of connected subgraphs of various sizes. Algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph's reliability polynomial. We develop a new bottom-up SIS algorithm for estimating the reliability polynomial by choosing a spanning tree and adding edges. This algorithm improves on existing bottom-up algorithms in that it has lower complexity O(E2V) as opposed to O(EV3), and it uses importance sampling to reduce variance.Proceedings Title
Winter Simulation Conference
Conference Dates
December 11-14, 2011
Conference Location
Phoenix, AZ, US
Pub Type
Conferences
Download Paper
Keywords
Monte Carlo methods, reliability, reliabilty polynomial, importance sampling
Citation
Created December 10, 2011, Updated October 12, 2021