Two Algorithms For Computing K-Terminal Network Reliability

Concerning about the reliability problems of computer communication networks, we mainly discuss the calculation of the network reliability. Two new algorithms for computing the K-terminal network reliability are presented.1 Ordered Binary Decision Diagram (OBDD) is one of the most efficient tools for computing network reliability. The reliability problem of a network from a source s to a set K of specified terminals (SKT) is discussed. Two gate variable reduction principles, algorithms of computing K-trees and minimum K-cuts of a network are proposed firstly. And then using Boolean equations containing gate variables and means of OBDD, an efficient algorithm for computing the K-terminal reliability of a network is also proposed. This algorithm is efficient, as demonstrated by experimental results. It has clear structure, fast speed and is easily implemented. This algorithm improves and generalizes the algorithm presented by Rauzy[77].2 Edge reduction diagram is an efficient method of computing cuts of a terminal-pair network. Improving and generalizing the algorithm presented by Yung-Ruei Chang etc.[82], an efficient algorithm for computing the K-terminal network reliability is proposed. This algorithm constructs | K | terminal-pair networks with source and every terminal of a set K of terminals firstly, and then applies edge reduction diagram to compute cuts of these terminal-pair networks. Lastly, using a theorem of computing the K-terminal network reliability and means of OBDD, the K-terminal reliability of a network is calculated. This algorithm avoids the complexity of computing K-trees and K-cuts of a network. This algorithm is simple and efficient, as demonstrated by experimental results.