高级检索

    熊祥军, 邵方明, 张祖渊, 管建民. 直径限定可靠性计算的冗余边的检测算法[J]. 华东理工大学学报(自然科学版), 2020, 46(6): 843-848. DOI: 10.14135/j.cnki.1006-3080.20190124001
    引用本文: 熊祥军, 邵方明, 张祖渊, 管建民. 直径限定可靠性计算的冗余边的检测算法[J]. 华东理工大学学报(自然科学版), 2020, 46(6): 843-848. DOI: 10.14135/j.cnki.1006-3080.20190124001
    XIONG Xiangjun, SHAO Fangming, ZHANG Zuyuan, GUAN Jianmin. Detection Algorithm of Irrelevant Edges by Diameter Limited Reliability Calculation[J]. Journal of East China University of Science and Technology, 2020, 46(6): 843-848. DOI: 10.14135/j.cnki.1006-3080.20190124001
    Citation: XIONG Xiangjun, SHAO Fangming, ZHANG Zuyuan, GUAN Jianmin. Detection Algorithm of Irrelevant Edges by Diameter Limited Reliability Calculation[J]. Journal of East China University of Science and Technology, 2020, 46(6): 843-848. DOI: 10.14135/j.cnki.1006-3080.20190124001

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

    Detection Algorithm of Irrelevant Edges by Diameter Limited Reliability Calculation

    • 摘要: 本文给出了路径长度的新度量方法,将st-路分类为实际路径(RP),伪路径(PP),组合路径(CP)和包含特定边(SPE)的最短st-路,明确通过测量PP,RP和CP可以计算SPE的长度;同时提出了一种检测隐藏冗余边的算法,该算法的复杂度为多项式(O(n4))。实验结果表明了该算法的有效性。

       

      Abstract: 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.

       

    /

    返回文章
    返回