Bounds on maximum concurrent flow in random bipartite graphs

DOI10.1007/s11590-020-01543-wzbMath1459.90217OpenAlexW3005261803MaRDI QIDQ2228396

David W. Matula, Fernando E. Vilas, Eli V. Olinick

Publication date: 17 February 2021

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-020-01543-w

zbMATH Keywords

random graphsbipartite graphsmaximum concurrent flow problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Stochastic programming (90C15)

Uses Software

• Boost
• BGL
• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• A combinatorial approximation algorithm for concurrent flow problem and its application
• Diameters of random bipartite graphs
• Sparsest cuts and bottlenecks in graphs
• An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
• Asymptotic analysis of the flow deviation method for the maximum concurrent flow problem
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Linear time algorithms for finding sparsest cuts in various graph classes
• Polynomial flow-cut gaps and hardness of directed cut problems
• The maximum concurrent flow problem
• Efficient algorithms for the maximum concurrent flow problem
• A Theorem on Boolean Matrices
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: Bounds on maximum concurrent flow in random bipartite graphs