Uniform multicommodity flow through the complete graph with random edge-capacities

DOI10.1016/j.orl.2009.04.008zbMath1227.05158OpenAlexW2124501739MaRDI QIDQ1038093

David J. Aldous, Alexander D. Scott, Colin J. H. McDiarmid

Publication date: 17 November 2009

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://escholarship.org/uc/item/0h2400bt

zbMATH Keywords

graph colouringmulticommodity flow

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Stochastic network models in operations research (90B15) Coloring of graphs and hypergraphs (05C15) Flows in graphs (05C21)

Related Items

Weak disorder in the stochastic mean-field model of distance. II, Optimal Multicommodity Flow Through the Complete Graph with Random Edge Capacities, Uniform multicommodity flows in the hypercube with random edge‐capacities, Return to the Poissonian city

Cites Work

• Unnamed Item
• Integer and fractional packings in dense graphs
• Surfaces with minimal random weights and maximal flows: a higher dimensional version of first-passage percolation
• Near perfect coverings in graphs and hypergraphs
• Bulk transport properties and exponent inequalities for random resistor and flow networks
• Critical behavior for maximal flows on the cubic lattice
• Optimal flow through the disordered lattice
• First-passage percolation, network flows and electrical resistances
• Edge flows in the complete random-lengths network
• Cost–Volume Relationship for Flows Through a Disordered Network
• Dynamic Routing in Fully Connected Networks