Name
Abstract | ||
|---|---|---|
We give two results for multicommodity flows in the d-dimensional hypercube Qd with 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 to 21-dE[C] between all vertex pairs. Both results are best possible. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 437-463, 2017 |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1002/rsa.20672 | Random Struct. Algorithms |
Keywords | Field | DocType |
multicommodity flow,hypercube,random,capacity | Discrete mathematics,Mathematical optimization,Combinatorics,Vertex (geometry),Multi-commodity flow problem,Antipodal point,Mathematics,Hypercube | Journal |
Volume | Issue | ISSN |
50 | 3 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin McDiarmid | 1 | 1071 | 167.05 |
| Alex Scott | 2 | 251 | 40.93 |
| Paul Withers | 3 | 0 | 0.34 |