计算K-终端网络可靠度的一种新算法

An New Algorithm of Computing K-Terminal Network Reliability

讨论了由一个源点s到一个指定的点集K的网络可靠度问题。首先提出了两个网络门限变量化简原则及计算网络K-树和极小K-割的算法。然后,基于具有门限变量的布尔方程和有序二分决策图方法,给出网络K-终端可靠度算法。结果表明这种算法是有效的,改进并推广了Rauzy提出的算法。

The reliability problem of a network from a source s to some specified terminal points set K (SKT) is discussed. Two gate_varible_reducation 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. This algorithm improves and generalizes the algorithm presented by Rauzy.