Journal article icon

Journal article

Uniform multicommodity flows in the hypercube with random edge‐capacities

Abstract:
We give two results for multicommodity flows in thed-dimensional hypercubeQdwithindependent random edge-capacities distributed like a random variableCwhereP[C>0]>1/2.Firstly, with high probability asd→∞, the network can support simultaneous multicommodityflows of volume close toE[C]between all antipodal vertex pairs. Secondly, with high probability,the network can support simultaneous multicommodity flows of volume close to 21−dE[C]betweenall vertex pairs. Both results are best possible.
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1002/rsa.20672

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Statistics
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Institute
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Institute
Publisher:
Wiley Publisher's website
Journal:
Random Structures and Algorithms Journal website
Volume:
50
Issue:
3
Pages:
437–463
Publication date:
2016-11-07
Acceptance date:
2016-01-20
DOI:
ISSN:
1098-2418
URN:
uuid:ba3605f3-cbea-42b6-a097-9426d521de31
Source identifiers:
499852
Local pid:
pubs:499852

Terms of use


Metrics



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

TO TOP