Two Algorithms For Computing 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 reliability of a network are presented.1 The sum of disjoint products method is efficient for computing the reliability of a network. Combining Boolean algebra with Shannon's formula, a new algorithm using sum disjoint products (sdp) is presented. Compared with known sdp algorithms, this algorithm generates a morecompact re1iability formula.2 A radio broadcast network(RBN) is modeled by a probabilistic graphG with unreliable nodes and perfect edges. Although the 2-terminal reliability problem has been widely studied for networks with unreliable links, a little is known about the problem for networks with unreliable nodes. Several reliability preserving reductions for the graph G are given. Using these reductions, firstly some edges of the graph G can be deleted, secondly the resulting graph G1 can be changed to a directedgraph G2, thirdly the directed graph G2 can be redacted to a directed graph G3 , and finally the reliability of the grapn G can be obtained by appling a sdp algorithm or a factoring algorithm to the directed graph G3 . The examples show that the reliability reserving reductions are efficient in computing the reliability of larger size RBN.