An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
From MaRDI portal
Publication:1894701
DOI10.1007/BF01200755zbMath0837.68045OpenAlexW1992520677MaRDI QIDQ1894701
R. Ravi, Ajit Agrawal, Satish B. Rao, Philip N. Klein
Publication date: 16 April 1996
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01200755
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27)
Related Items (13)
Primal-dual approximation algorithms for feedback problems in planar graphs ⋮ Approximation algorithms for requirement cut on graphs ⋮ Improved bounds on the max-flow min-cut ratio for multicommodity flows ⋮ Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ The multi-multiway cut problem ⋮ Unnamed Item ⋮ Approximating the fixed linear crossing number ⋮ Approximating Requirement Cut via a Configuration LP ⋮ An improved approximation algorithm for requirement cut ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
Cites Work
- Approximation algorithms for combinatorial problems
- Tough graphs and Hamiltonian circuits.
- The maximum concurrent flow problem
- A Heuristic Algorithm for Small Separators in Arbitrary Graphs
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Graph Bipartization and via minimization
- Edge-Deletion Problems
- New problems complete for nondeterministic log space
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
- A graph-theoretic via minimization algorithm for two-layer printed circuit boards
- Excluded minors, network decomposition, and multicommodity flow
- Improved bounds on the max-flow min-cut ratio for multicommodity flows
- Approximate max-flow min-(multi)cut theorems and their applications
- Multi-Commodity Network Flows
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
