计算无圈有向网络ST可靠性的一个新方法

本文考虑计算无圈有向网络的ＳＴ可靠性问题（至少存在一条从源点ｓ到汇点ｔ的正常运行道路的概率）。文章引进了深度优先搜索（Ｄｅｐｔｈ－ＦｉｒｓｔＳｅａｒｃｈ）有序根树的概念并提出一个新的计算无圈有向网络ＳＴ可靠性的拓扑公式。以该公式为基础,我们利用ＤＦＳ方法提出一个新的计算无圈有向网络ＳＴ可靠性算法,它能生成简洁的可靠性表达式,进而有效地计算无圈有向网络的ＳＴ可靠性。两个例子例证了我们的结论     

基于容斥原理与不交和公式的一个计算网络可靠性方法

这篇文章考虑了网络从源点ｓ到某些特定终点Ｋ的ＳＫＴ可靠性问题，文章基于容斥原理和不交和公式提出的一个新的拓扑公式，它比相应的Ｓａｔｙａｎａｒａｙａｎｎａ公式含有更少的项和算术运算，在此公式基础上，提出一个计算网络ＳＫＴ可靠性算法，它改进了相应的Ｓａｔｙａｎａｒａｙｍａｎｎａ算法，能产生更紧的可靠性表达式。     

无线广播网络的可靠性分析

本文提出了一个计算无线广播网络的Ｋ－终点可靠度方法。因为ＲＢＮ的Ｋ－终点可靠度问题是个ＮＰ－困难问题,所以已有的结果只是一些近似算法和针对某些特殊ＲＢＮ的算法。     

计算两类网络的可靠性的多项式时间算法

定义了两类有向网络——ORC-网络和IRC-网络,并且提出一个计算它们的根通信可靠性(网络的一个特定结点(根点)能与其余每个结点通信的概率)的多项式时间算法.对于ORC-网络和IRC-网络,该算法的时间复杂度分别是O(｜E｜)和O(｜V｜·｜E｜),这里,｜V｜,｜E｜分别表示网络所含结点和边的数量.     

利用因子分解方法计算网络的根通信可靠性

本文使用因子分解(factoring)的方法计算网络的根通信可靠性(存在从根点到每一个其它结点正常运行道路的概率)。我们充分利用无圈有向网络的拓扑结构提出了两个新的可靠性保护缩减(Reliability-Preserving Reduction)和一个进行因子分解的选边规则。在此基础上,给出一个因子分解算法(factoring algorithm)。对于不是非常稠密的网络,该算法是非常有效的。