| 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: |
 Click here to retrieve PDF version of paper (228KB) |
