Abstract:
The evaluation of source to terminal(
s-
t) reliability of a network is classed in the NP hard family.The exact computation method of large networks is extremely time-consuming.Therefore,approximate computation methods are generally used.One feasible approximation approach is to use bounds.This paper proposes a directly disjoint algorithm using bounds for
s-
t reliability evaluation of large networks.This algorithm can obtain disjoint minimal path and disjoint minimal cut without prior enumeration of minimal path or minimal cut.On the principle of breadth-first search and minimal-distance-first search,the algorithm can get exact solution of simple networks and approximation of large networks with real-time accumulation of disjoint minimal paths and cuts.Compared with the modified Dotson algorithm,this algorithm is faster in solving the reliability of large network with low element operation probability.Compared with the minimal cut-based recursive decomposition algorithm,a more optimum disjoint set can be obtained by this algorithm.