1991年10月
MAXIMUM FLOWS IN PROBABILISTIC NETWORKS
NETWORKS
- ,
- 巻
- 21
- 号
- 6
- 開始ページ
- 645
- 終了ページ
- 666
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1002/net.3230210604
- 出版者・発行元
- JOHN WILEY & SONS INC
The reliability of capacitated networks subject to random arc failures is evaluated by the expected value of maximum flow. It is known that calculating the expected value of maximum flow is NP-hard, but a lower bound can be efficiently computed by the method of Carey and Hendrickson. This bound sometimes gives the exact value, e.g., if graphs are bipartite. In this article, for directed and undirected networks, respectively, we give necessary and sufficient conditions for the above lower bound to provide the exact value.
- リンク情報
- ID情報
-
- DOI : 10.1002/net.3230210604
- ISSN : 0028-3045
- Web of Science ID : WOS:A1991GF55900003