Efficient computation of terminal-pair reliability using triangle reduction in network management
Efficient computation of terminal-pair reliability using triangle reduction in network management
复制标题
网络管理中使用三角简化有效计算终端对可靠性
DOI：
10.1109/icc.1998.682686
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
M. Yuang
中科院分区：
文献类型：
--
作者：
S. J. Hsu;M. Yuang
网络管理中的终端对可靠性（TR）确定了网络中两个节点（源和宿）之间的概率可靠性，给定所有链路的故障概率。它已被证明，TR可以有效地计算通过网络简化技术。现有的归约公理，不幸的是，仅限于简单的规则，如无价值的链接删除和串并联链接减少。我们提出了一个新的减少公理，称为三角形减少。三角形归约公理将包含三角形子图的图变换为不包含三角形底的图。变换的计算复杂度低至O（1）。本文进一步从子问题数量和计算时间方面评估了三角形约简对基于划分的TR算法的有效性。实验结果表明，结合三角形约简，分区为基础的TR算法产生的子问题和计算时间的所有基准和随机网络的数量大大减少。
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. 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.