Algebraic methods for stochastic minimum cut and maximum flow problems
2011
We present an algebraic approach for computing the distribution of the capacity of a minimum s-t cut in a network, in which the arc capacities have known (discrete) probability distributions. Algorithms are developed to determine the exact distribution as well as upper and lower bounding distributions on the capacity of a minimum cut. This approach then provides exact and bounding distributions on the maximum flow in such stochastic networks. We also obtain bounds on the expected capacity of a minimum cut (and the expected maximum flow value).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
15
References
5
Citations
NaN
KQI