Skip to main content
Uniform multicommodity flow through the complete graph with random edge-capacities
- Author(s): Aldous, DJ
- McDiarmid, C
- Scott, A
- et al.
Published Web Location
https://doi.org/10.1016/j.orl.2009.04.008Abstract
Give random capacities C to the edges of the complete n-vertex graph. Consider the maximum flow Φnthat can be simultaneously routed between each source-destination pair. We prove that Φn→ φ{symbol} in probability where the limit constant φ{symbol} 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. © 2009 Elsevier B.V. All rights reserved.
Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.