On the Max-flow min-cut ratio for directed multicommodity flows

DOI10.1016/j.tcs.2005.10.037zbMath1090.90014OpenAlexW2059920516MaRDI QIDQ818146

Mohammad Taghi Hajiaghayi, Leighton, Tom

Publication date: 24 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.037

zbMATH Keywords

approximation algorithmdirected graphmulticommodity flow and multicut

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Approximation algorithms (68W25)

Related Items (3)

On the complexity of the multicut problem in bounded tree-width graphs and digraphs ⋮ On the hardness of finding near-optimal multicuts in directed acyclic graphs ⋮ An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound on the integrality gap for minimum multicut in directed networks
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

This page was built for publication: On the Max-flow min-cut ratio for directed multicommodity flows