K-Terminal Network Reliability Measures With Binary Decision Diagrams |
| |
Authors: | Hardy G. Lucet C. Limnios N. |
| |
Affiliation: | Univ. de Picardie Jules Verne, Amiens; |
| |
Abstract: | We present a network decomposition method using binary decision diagrams (BDD), a state-of-the-art data structure to encode, and manipulate Boolean functions, for computing the reliability of networks such as computer, communication, or power networks. We consider the K-terminal reliability measure RK, which is defined as the probability that a subset K of nodes can communicate with each other, taking into account the possible failures of the network links. We present an exact algorithm for computing the if-terminal reliability of a network with perfect vertices in O(m.Fmax .2Fmax.BFmax), where BFmax is the Bell number of the maximum boundary set of vertices Fmax, and m is the number of network links. Several examples, and experiments show the effectiveness of this approach. |
| |
Keywords: | |
|
|