論文

査読有り
1991年10月

MAXIMUM FLOWS IN PROBABILISTIC NETWORKS

NETWORKS
  • H NAGAMOCHI
  • ,
  • T IBARAKI

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.

リンク情報
DOI
https://doi.org/10.1002/net.3230210604
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:A1991GF55900003&DestApp=WOS_CPL
ID情報
  • DOI : 10.1002/net.3230210604
  • ISSN : 0028-3045
  • Web of Science ID : WOS:A1991GF55900003

エクスポート
BibTeX RIS