Premium
Uniform multicommodity flows in the hypercube with random edge‐capacities
Author(s) -
McDiarmid Colin,
Scott Alex,
Withers Paul
Publication year - 2017
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20672
Subject(s) - hypercube , mathematics , vertex (graph theory) , antipodal point , random variable , combinatorics , enhanced data rates for gsm evolution , discrete mathematics , computer science , graph , statistics , geometry , telecommunications
We give two results for multicommodity flows in the d ‐dimensional hypercubeQ dwith independent random edge‐capacities distributed like a random variable C where ℙ [ C > 0 ] > 1 / 2 . Firstly, with high probability as d → ∞ , the network can support simultaneous multicommodity flows of volume close to E [ C ] between all antipodal vertex pairs. Secondly, with high probability, the network can support simultaneous multicommodity flows of volume close to2 1 − d E [ C ] between all vertex pairs. Both results are best possible. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 437–463, 2017