Journal article icon

Journal article

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

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.
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1016/j.orl.2009.04.008

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Inst
Role:
Author
Journal:
Oper. Res. Lett.
Volume:
37
Issue:
5
Pages:
299-302
Publication date:
2009-01-01
DOI:
ISSN:
0167-6377
URN:
uuid:533af27f-75f9-4698-a19a-6b79d3c44ca4
Source identifiers:
102282
Local pid:
pubs:102282
Language:
English
Keywords:

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP