计算 3-Tree 网络全终端可靠度的线性时间算法

A Linear Time Algorithm to Compute the Reliability of 3 Tree Networks

对于一般网络，计算全终端可靠度是ＮＰ难问题．３Ｔｒｅｅ网络是一类具有特殊结构和性质的网络．利用三角子图到Ｋ４的化简，给出了一个计算３Ｔｒｅｅ网络全终端可靠度的线性时间算法．

Computing R(G) for general graphs is a NP hard problem.3 tree networks are a class of special networks. An O(|V|) time algorithm to compute the all terminal reliability of 3 tree networks is presented.