网络端端可靠度的上下界计算研究  

Research on computing the upper and lower bound of network terminal to terminal reliability

作　　者：乔晓东[1] 毛志[1] 邓宏钟[1] 

机构地区：[1]国防科技大学信息系统与管理学院,湖南长沙410073

出　　处：《电子设计工程》2011年第17期94-97,共4页Electronic Design Engineering

基　　金：国家自然科学基金资助项目(70771111;60904065);高等学校博士点专项基金资助项目(20094307120001)

摘　　要：考虑精确计算较大规模网络的端端可靠度属于NP-hard问题,提出一种计算网络端端可靠度的近似方法,算法分别基于最小路集和不交最短路集来计算网络端端可靠度的上下界,并在此基础上给出了示例来阐明算法的有效性,该计算方法的算法实现简单,能快速计算出网络的端端相对可靠度。A approximate method of computing network terminal to terminal reliability is presented, because the accurate method is proved to be a NP-hard problem. The proposed algorism is based on minimal path sets and disjoint shortest path sets to compute the upper and lower bound of terminal tO terminal reliability, on the basis of the method, results show that the algorithm feasible and effective. It is also simple carried out on computer, and can compute the relative terminal to terminal reliability of network quickly.

关 键 词：端端可靠性 上界 下界 最小路 不交路 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]