Take a sneak peek at the new NIST.gov and let us know what you think!
(Please note: some content may not be complete on the beta site.).
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.|
|Pages:||pp. 143 - 151|
|Keywords:||reliability polynomial, randomized algorithm|
|PDF version:||Click here to retrieve PDF version of paper (234KB)|