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

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

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

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.