Cloteaux, B.
, Beichl, I.
and Sullivan, F.
(2010),
An Approximation Algorithm for the Coefficients of the Reliability Polynomial, Congressus Numerantium, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=902705
(Accessed April 17, 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.
An Approximation Algorithm for the Coefficients of the Reliability Polynomial
Published
Author(s)
, ,
Abstract
The reliability polynomial gives the probability that a graph remains connected given that each edge in it can fail independently with a probability p. While in general determining the coefficients of this polynomial is #P-complete, we give a randomized algorithm for approximating its coefficients. When compared to the known approximation method of Colbourn, Debroni and Myrvold, our method empirically shows a much faster rate of convergence.Citation
Congressus Numerantium
Volume
197
Pub Type
Journals
Download Paper
Keywords
reliability polynomial, randomized algorithm
Citation
Created March 15, 2010, Updated February 19, 2017