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

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

0.00 Avg rating0 Votes
Article ID: iaor20102996
Volume: 37
Issue: 5
Start Page Number: 299
End Page Number: 302
Publication Date: Sep 2009
Journal: Operations Research Letters
Authors: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.