Author
McDiarmid, C
Scott, A
Withers, P
Journal title
Random Structures and Algorithms
Last updated
2024-05-10T11:58:33.61+01:00
Abstract
We give two results for multicommodity flows in the $d$-dimensional hypercube
${Q}^d$ with independent random edge capacities distributed like $C$ where
$\Pr[C>0]>1/2$. Firstly, with high probability as $d \rightarrow \infty$, 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 to
$2^{1-d} E[C]$ between all vertex pairs. Both results are best possible.
Symplectic ID
499852
Download URL
http://arxiv.org/abs/1406.4433v3
Favourite
Off
Publication type
Journal Article
Please contact us with feedback and comments about this page. Created on 19 Dec 2014 - 12:05.