Premium
Maximum flows in probabilistic networks
Author(s) -
Nagamochi Hiroshi,
Ibaraki Toshihide
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210604
Subject(s) - maximum flow problem , upper and lower bounds , bipartite graph , probabilistic logic , flow (mathematics) , value (mathematics) , combinatorics , flow network , mathematics , computer science , reliability (semiconductor) , arc (geometry) , directed graph , mathematical optimization , discrete mathematics , graph , statistics , geometry , physics , mathematical analysis , power (physics) , quantum mechanics
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.