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

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

考虑精确计算较大规模网络的端端可靠度属于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.