Uniform multicommodity flow through the complete graph with random edge-capacities.
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}...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2009
|
| _version_ | 1797068804924112896 |
|---|---|
| author | Aldous, D McDiarmid, C Scott, A |
| author_facet | Aldous, D McDiarmid, C Scott, A |
| author_sort | Aldous, D |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T22:15:24Z |
| format | Journal article |
| id | oxford-uuid:533af27f-75f9-4698-a19a-6b79d3c44ca4 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T22:15:24Z |
| publishDate | 2009 |
| record_format | dspace |
| spelling | oxford-uuid:533af27f-75f9-4698-a19a-6b79d3c44ca42022-03-26T16:30:13ZUniform multicommodity flow through the complete graph with random edge-capacities.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:533af27f-75f9-4698-a19a-6b79d3c44ca4EnglishSymplectic Elements at Oxford2009Aldous, DMcDiarmid, CScott, AGive 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. |
| spellingShingle | Aldous, D McDiarmid, C Scott, A Uniform multicommodity flow through the complete graph with random edge-capacities. |
| title | Uniform multicommodity flow through the complete graph with random edge-capacities. |
| title_full | Uniform multicommodity flow through the complete graph with random edge-capacities. |
| title_fullStr | Uniform multicommodity flow through the complete graph with random edge-capacities. |
| title_full_unstemmed | Uniform multicommodity flow through the complete graph with random edge-capacities. |
| title_short | Uniform multicommodity flow through the complete graph with random edge-capacities. |
| title_sort | uniform multicommodity flow through the complete graph with random edge capacities |
| work_keys_str_mv | AT aldousd uniformmulticommodityflowthroughthecompletegraphwithrandomedgecapacities AT mcdiarmidc uniformmulticommodityflowthroughthecompletegraphwithrandomedgecapacities AT scotta uniformmulticommodityflowthroughthecompletegraphwithrandomedgecapacities |