文献类型：期刊文献

中文题名：直径限定可靠性计算的冗余边的检测算法

英文题名：Detection Algorithm of Irrelevant Edges by Diameter Limited Reliability Calculation

作者：熊祥军[1];邵方明[1];张祖渊[1];管建民[2]

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

年份：2020

卷号：46

期号：6

起止页码：843

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;Scopus;北大核心:【北大核心2017】；CSCD:【CSCD_E2019_2020】；

语种：中文

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

外文关键词：diameter constraint;irrelevant edges;reliability;algorithm

摘要：本文给出了路径长度的新度量方法,将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.