TY - CHAP

T1 - Efficient computation of terminal-pair reliability using triangle reduction in network management

AU - Hsu, Steen J.

AU - Yuang, Maria C.

PY - 1998/1/1

Y1 - 1998/1/1

N2 - 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 simple 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). 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. Experimental results demonstrate that, incorporating triangle reduction, the partition-based TR algorithms yield a substantially reduced number of subproblems and computation time for all benchmarks and random networks.

AB - 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 simple 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). 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. Experimental results demonstrate that, incorporating triangle reduction, the partition-based TR algorithms yield a substantially reduced number of subproblems and computation time for all benchmarks and random networks.

UR - http://www.scopus.com/inward/record.url?scp=0031619484&partnerID=8YFLogxK

M3 - Chapter

AN - SCOPUS:0031619484

T3 - IEEE International Conference on Communications

SP - 281

EP - 285

BT - IEEE International Conference on Communications

A2 - Anon, null

PB - IEEE

Y2 - 7 June 1998 through 11 June 1998

ER -