Article ID: | iaor20131718 |
Volume: | 25 |
Issue: | 1 |
Start Page Number: | 56 |
End Page Number: | 71 |
Publication Date: | Dec 2013 |
Journal: | INFORMS Journal on Computing |
Authors: | Rubino Gerardo, L'Ecuyer Pierre, Tuffin Bruno, Simard Richard, Botev Zdravko I |
Keywords: | graphs, networks, quality & reliability |
We propose a novel simulation‐based method that exploits a generalized splitting (GS) algorithm to estimate the reliability of a graph (or network), defined here as the probability that a given set of nodes are connected, when each link of the graph fails with a given (small) probability. For large graphs, in general, computing the exact reliability is an intractable problem and estimating it by standard Monte Carlo methods poses serious difficulties, because the