Uniform multicommodity flows in the hypercube with random edge‐capacities | Zendy

McDiarmid Colin | Zendy; Scott Alex | Zendy; Withers Paul | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research