计算多级互联网络可靠度的一个算法

An Algorithm to Compute the Reliability of Multistage Interconnection Network

利用根有向树给出一个求有效路径的算法，从而得到一个计算多级互联网络可靠度的简捷方法。求网络可靠度时，该算法的计算量和文献[1]中算法相当；而求两终端可靠度时，计算量是文献[1]中算法的2／N倍（这里N是MIN的输入站或输出站的数目）；求K－终端可靠度时，计算量也要比文献[1]中算法小。因此本文算法是一个计算多级互联网络可靠度的一个有效算法。

Gives an algorithm to find effective paths by using the rooted directed tree. A simple algorithm tocompute the reliability of multistage interconnection networks is obtained. The computational time of the al－gorithm for network reliability is the same as that of ref. [1],for two terminal re1iability is 2/N times that ofref. [1](where N is the input or output number of MIN), for k－terminal reliability is much smaller than thatof ref. [1]. Therefore, this algorithm is efficient in computing the reliability of multistage inter－connectionnetworks.