Efficient computation of marginal reliability-importance for reducible + networks

Steen J. Hsu*, Maria C. Yuang

*Corresponding author for this work

Research output: Contribution to journalArticle

7 Scopus citations


Marginal reliability importance (MRI) of a link with respect to terminal-pair reliability (TR) is the rate to which TR changes with the modification of the success probability of the link. It is a quantitative measure reflecting the importance of the individual link in contributing to TR of a given network. Computing MRI for general networks is an NP-complete problem. Attention has been drawn to a particular set of networks (reducible networks), which can be simplified to source-sink (2-node) networks via 6 simple reduction rules (axioms). The computational complexity of the MRI problem for such networks is polynomial bounded. This paper proposes a new reduction rule, referred to as triangle reduction. The triangle reduction rule transforms a graph containing a triangle subgraph to that excluding the base of the triangle, with constant complexity. Networks which can be fully reduced to source-sink networks by the triangle reduction rule, in addition to the 6 reduction rules, are further defined as reducible + networks. For efficient computation of MRI for reducible + networks, a 2-phase (2-P) algorithm is given. The 2-P algorithm performs network reduction in phase 1. In each reduction step, the 2-P algorithm generates the correlation, quantified by a reduction factor, between the original network and the reduced network. In phase 2, the 2-P algorithm backtracks the reduction steps and computes MRI, based on the reduction factors generated in phase 1 and a set of closed-form TR formulas. As a result, the 2-P algorithm yields a linearly bounded complexity for the computation of MRI for reducible + networks. Experimental results from real networks and benchmarks show the superiority, by two orders of magnitude, of the 2-P algorithm over the traditional approach.

Original languageEnglish
Pages (from-to)98-106
Number of pages9
JournalIEEE Transactions on Reliability
Issue number1
StatePublished - 1 Mar 2001


  • Marginal reliability importance (MRI)
  • Network reduction technique
  • Reducible network
  • Terminal-pair reliability (TR)

Fingerprint Dive into the research topics of 'Efficient computation of marginal reliability-importance for reducible <sup>+</sup> networks'. Together they form a unique fingerprint.

  • Cite this