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

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

  • Author(s): Aldous, DJ
  • McDiarmid, C
  • Scott, A
  • et al.

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.

Main Content
Current View