Improved bounds on the max-flow min-cut ratio for multicommodity flows

DOI10.1007/BF01299746zbMath0833.68067OpenAlexW2610755752MaRDI QIDQ1900189

Éva Tardos, Serge A. Plotkin

Publication date: 11 March 1996

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01299746

zbMATH Keywords

multicommodity flow problemspolynomial time approximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ Multicommodity flows and cuts in polymatroidal networks

Cites Work

• Unnamed Item
• Multicommodity flows in planar graphs
• Matroids and multicommodity flows
• Approximating minimum feedback sets and multicuts in directed graphs
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Packing directed circuits fractionally
• Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
• Improved approximations for the minimum-cut ratio and the flux
• Excluded minors, network decomposition, and multicommodity flow
• Approximate max-flow min-(multi)cut theorems and their applications