计算一类网络K—终点可靠性的线性时间算法  

Linear Time Algorithm for K-Terminal Reliability of WST Networks

作　　者：高飞[1] 王光兴[1] 

机构地区：[1]东北大学信息学院,辽宁沈阳110003

出　　处：《小型微型计算机系统》2005年第2期192-194,共3页Journal of Chinese Computer Systems

基　　金：国家自然科学基金 (69973 0 11)资助 .

摘　　要：可靠性保护缩减的方法是计算网络可靠性的常用手段之一 ,而且关心哪类网络的可靠性存在线性时间算法 .给出了一类新的可靠性保护缩减—桥缩减和一类无向网络 ,称之为 WST网络 ,该类网络是对串并联网络的扩展并且对该类网络提出了一个计算 K—终点可靠性的线性时间算法 ,其算法复杂性为 O(|E|2 ) .Reliability preserving reduction method for computing K terminal reliability of networks used in this paper is one of method of computing networks reliability. One class of new reliability preserving reduction Wstone bridge reduction and a class of networks namely WST networks are presented. The networks is an extension to S P networks .Based on this ,we give a new linear time algorithm for computing K terminal reliability of this class networks, the complexity of algorithm is O(|E| 2).

关 键 词：网络 网络可靠性 可靠性保护缩减 

分 类 号：TN913[电子电信—通信与信息系统]