Article ID Journal Published Year Pages File Type
1143389 Operations Research Letters 2009 4 Pages PDF
Abstract
Give random capacities C to the edges of the complete n-vertex graph. Consider the maximum flow Φn that can be simultaneously routed between each source-destination pair. We prove that Φn→ϕ in probability where the limit constant ϕ depends on the distribution of C in a simple way, and that asymptotically one need use only 1- and 2-step routes. The proof uses a reduction to a random graph problem.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,