ON ONAGAS UPPER BOUND ON THE MEAN-VALUES OF PROBABILISTIC MAXIMUM FLOWS

被引：4
|
作者：
NAGAMOCHI, H
IBARAKI, T
机构：
[1] Kyoto University, Kyoto
来源：
IEEE TRANSACTIONS ON RELIABILITY | 1992年 / 41卷 / 02期
关键词：
UNDIRECTED GRAPH; DIRECTED GRAPH; PROBABILISTIC NETWORK; MAXIMUM FLOW; MINIMUM CUT; POLYNOMIAL TIME ALGORITHM;
D O I：
10.1109/24.257785
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
The reliability of capacity-limited networks subject to are failures can be evaluated by the mean value of maximum flow. Calculating the mean value of maximum flow is NP-hard. However, the Onaga upper bound sometimes gives the exact value, eg, when graphs are bipartite. This paper gives for networks (whether arcs are directed or not) a necessary and sufficient condition for the Onaga upper bound to be exact.
引用
收藏
页码：225 / 229
页数：5
相关论文
共 50 条
12345