|
|||||
|
|
Uniform multicommodity flow through the complete graph with random edge-capacities |
|
| Authors: | David J. Aldous |
| Affiliation: | a Department of Statistics, University of California, Berkeley, CA 94720-3860, USA b Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, UK c Mathematical Institute, University of Oxford, 24-29 St Giles, Oxford OX1 3LB, UK |
| 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. |
| Keywords: | Multicommodity flow Graph colouring |
| 本文献已被 ScienceDirect 等数据库收录！ | |