Detection Algorithm of Irrelevant Edges by Diameter Limited Reliability Calculation

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(n⁴)). Experimental results show the efficiency of the algorithm.