A Recursive Algorithm for Computing Exact Reliability Measures

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.