Network reduction axiom for efficient computation of terminal-pair reliability

S. J. Hsu*, Maria C. Yuang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Terminal-pair reliability (TR) in network management determines the probabilistic reliability between two nodes (the source and sink) of a network, given failure probabilities of all links. It has been shown that TR can be effectively computed by means of the network reduction technique. Existing reduction axioms, unfortunately, are limited to trivial rules such as valueless link removal and series-parallel link reduction. In this paper, we propose a novel reduction axiom, referred to as triangle reduction. The triangle reduction axiom transforms a graph containing a triangle subgraph to that excluding the base of the triangle. The computational complexity of the transformation is as low as O(1). With triangle reduction, the number of subproblems generated by partition-based TR algorithms, for simplified grid networks, can be reduced to O(((1 + √5)/2)n). The paper further provides an assessment of the effectiveness of triangle reduction on partition-based TR algorithms with respect to the number of subproblems and computation time through experimenting on published benchmarks and random networks. Experimental results demonstrate that, incorporating triangle reduction, the path-based (cut-based) partition TR algorithm yields a substantially reduced number of subproblems and computation time for all (most of the) benchmarks and random networks.

Original languageEnglish
Pages (from-to)359-372
Number of pages14
JournalComputers and Mathematics with Applications
Volume40
Issue number2
DOIs
StatePublished - 1 Jan 2000

Fingerprint Dive into the research topics of 'Network reduction axiom for efficient computation of terminal-pair reliability'. Together they form a unique fingerprint.

Cite this