NIST logo

Publication Citation: An Approximation Algorithm for the Coefficients of the Reliability Polynomial

NIST Authors in Bold

Author(s): Brian D. Cloteaux; Isabel M. Beichl; F Sullivan;
Title: An Approximation Algorithm for the Coefficients of the Reliability Polynomial
Published: March 15, 2010
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
Pages: pp. 143 - 151
Keywords: reliability polynomial; randomized algorithm
Research Areas: Modeling
PDF version: PDF Document Click here to retrieve PDF version of paper (234KB)