Skip to main content
eScholarship
Open Access Publications from the University of California
Refine Search

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

Uniform multicommodity flow through the complete graph with random edge-capacities

Published Web Location

https://doi.org/10.1016/j.orl.2009.04.008
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 → φ{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's open access policies. Let us know how this access is important for you.


Top