A Memory-efficient Bounding Algorithm for the Two-terminal Reliability Problem
A Memory-efficient Bounding Algorithm for the Two-terminal Reliability Problem
复制标题
一种解决两端可靠性问题的内存高效限界算法
DOI：
10.1016/j.entcs.2012.11.015
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
J. Weidendorfer
中科院分区：
文献类型：
--
作者：
M. Lê;M. Walter;J. Weidendorfer
终端对可靠性问题，即确定存在至少一条连接终端节点的工作边路径的概率的问题，已知是NP难的。因此，边界算法用于科普大的图形尺寸。然而，它们在内存方面仍然有巨大的需求。我们提出了一个内存效率的实现Gobien-Dotson边界算法的扩展。在不增加运行时间的情况下，相关数据结构的压缩允许我们使用低带宽高容量存储。这样，可用的硬盘空间就成为限制因素。根据输入结构，可以处理具有数百条边的图（即系统组件）。
The terminal-pair reliability problem, i.e. the problem of determining the probability that there exists at least one path of working edges connecting the terminal nodes, is known to be NP-hard. Thus, bounding algorithms are used to cope with large graph sizes. However, they still have huge demands in terms of memory. We propose a memory-efficient implementation of an extension of the Gobien-Dotson bounding algorithm. Without increasing runtime, compression of relevant data structures allows us to use low-bandwidth high-capacity storage. In this way, available hard disk space becomes the limiting factor. Depending on the input structures, graphs with several hundreds of edges (i.e. system components) can be handled.
网络管理中使用三角简化有效计算终端对可靠性
DOI：
10.1109/icc.1998.682686
发表时间：
1998
期刊：
ICC '98. 1998 IEEE International Conference on Communications. Conference Record. Affiliated with SUPERCOMM'98 (Cat. No.98CH36220)
影响因子：
--
作者：
S. J. Hsu;M. Yuang
通讯作者：
M. Yuang
具有相关基本事件的两端网络可靠性的界限
DOI：
10.1007/978-3-642-28540-0_3
发表时间：
2012
期刊：
影响因子：
--
作者：
M. Lê;M. Walter
通讯作者：
M. Walter