直径限定可靠性计算的冗余边的检测算法  

Detection Algorithm of Irrelevant Edges by Diameter Limited Reliability Calculation

作　　者：熊祥军 邵方明[1] 张祖渊 管建民 XIONG Xiangjun;SHAO Fangming;ZHANG Zuyuan;GUAN Jianmin(School of Science,East China University of Science and Technology,Shanghai 200237,China;Department of Mathematics,Changchun University of Finance and Economics,Changchun 130122,China)

机构地区：[1]华东理工大学理学院,上海200237 [2]长春财经学院数学系,长春130122

出　　处：《华东理工大学学报（自然科学版）》2020年第6期843-848,共6页Journal of East China University of Science and Technology

摘　　要：本文给出了路径长度的新度量方法,将st-路分类为实际路径(RP),伪路径(PP),组合路径(CP)和包含特定边(SPE)的最短st-路,明确通过测量PP,RP和CP可以计算SPE的长度;同时提出了一种检测隐藏冗余边的算法,该算法的复杂度为多项式(O(n4))。实验结果表明了该算法的有效性。A polynomial-time topological reduction plays an important role in the computation of diameter constrained reliability,because many irrelevant edges are able to be deleted and the reliability remains unchanged.However,irrelevant edges cannot be completely found from previous researches.The necessary condition of detecting irrelevant edges is a so-called open problem.In this paper,we define new metrics of path lengths,classify st-paths as real path(RP),pseudo path(PP),combination path(CP)and the shortest st-path containing a specific edge(SPE),and make it clear that the length of SPE can be approached by measuring PPs,RPs and CPs.Further,we propose an algorithm to detect innermost irrelevant edges and the complexity of the algorithm is polynomial(O(n4)).Experimental results show the efficiency of the algorithm.

关 键 词：直径限制 冗余边 可靠性 算法 

分 类 号：O29[理学—应用数学]