Name
Abstract | ||
|---|---|---|
Give random capacities C to the edges of the complete n-vertex graph. Consider the maximum flow @F"n that can be simultaneously routed between each source-destination pair. We prove that @F"n-@f in probability where the limit constant @f 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.orl.2009.04.008 | Oper. Res. Lett. |
Keywords | Field | DocType |
multicommodity flow,complete graph,maximum flow,2-step route,random edge-capacities,graph colouring,random graph problem,uniform multicommodity flow,source-destination pair,random capacity,multicommodity,complete n-vertex graph,random graph | Discrete mathematics,Random regular graph,Complete graph,Combinatorics,Mathematical optimization,Line graph,Random graph,Null graph,Graph bandwidth,Butterfly graph,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
37 | 5 | Operations Research Letters |
Citations | PageRank | References |
1 | 0.38 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David J. Aldous | 1 | 40 | 7.12 |
| Colin McDiarmid | 2 | 1071 | 167.05 |
| Alex Scott | 3 | 251 | 40.93 |