计算一类有向网络可靠性的线性时间算法

该文使用的可靠性保护缩减的方法计算有向网络ST可靠性（存在从源点到汇点正常运行道路的概率）是计算网络可靠性的常用方法之一，而且人们非常关心怎样的网络计算其可靠性存在线性时间算法，作者提出了两类新的可靠性保护缩减－－源桥缩减和惠斯通桥缩减和一类有向无圈网络，称之为WST网络，该类网络是对以前的BSP网络的扩展并且对于该类网络提出了一个计算其可靠性的线性时间算法。

A Linear Time Algorithm for Computing ST Reliability of A Class of Directed Networks

Reliability preserving reduction method for computing ST reliability of networks used in this paper is one of the method of computing network reliability, i.e. the probability that there are operating paths from a root vertex to a terminal vertex. Two classes of new reliability preserving reductions, source bridge reductions and Wstone bridge reduction, and a class of directed networks namely WST networks, are presented. The network is an extension to BSP networks. Based on those, we give a new linear time algorithm for computing this class of networks.