Improved bounds on the max-flow min-cut ratio for multicommodity flows
From MaRDI portal
Publication:5248540
DOI10.1145/167088.167263zbMath1310.68095OpenAlexW2018279087MaRDI QIDQ5248540
Publication date: 7 May 2015
Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/8927
Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21)
Related Items
A Mixed Integer Model for the Sparsest Cut problem ⋮ An approximate max-flow min-cut relation for undirected multicommodity flow, with applications ⋮ The geometry of graphs and some of its algorithmic applications ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover ⋮ Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
