A Recursive Algorithm for Computing Exact Reliability Measures
- 1 April 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Reliability
- Vol. 35 (1) , 36-40
- https://doi.org/10.1109/TR.1986.4335338
Abstract
An algorithm is presented to find source-to-K-terminal reliability in a directed graph with independent arc failures. The algorithm is based on a discrete-time Markov chain with two absorbing states. The Markov chain has an upper triangular transition probability matrix, thus the probability of absorption in a state can be found by back-substitution. We show: 1) The source-to-K-terminal reliability is the probability of absorption in a particular absorbing state; 2) The time until absorption can be used as an alternative reliability measure; and 3) The algorithm can be used to find a third reliability measure called the degree of connectedness.Keywords
This publication has 6 references indexed in Scilit:
- Computing Network Reliability in Time Polynomial in the Number of CutsOperations Research, 1984
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is ConnectedSIAM Journal on Computing, 1983
- A recursive algorithm for directed‐graph reliabilityNetworks, 1983
- A Unified Formula for Analysis of Some Network Reliability ProblemsIEEE Transactions on Reliability, 1982
- A recursive algorithm for finding reliability measures related to the connection of nodes in a graphNetworks, 1980
- New Topological Formula and Rapid Algorithm for Reliability Analysis of Complex NetworksIEEE Transactions on Reliability, 1978