An approximate max-flow min-cut relation for undirected multicommodity flow, with applications

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

zbMATH Keywords

multiway-cut problemundirected multicommodity flow

Mathematics Subject Classification ID

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 (16)

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 ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time ⋮ Max-flow min-cut theorem in quantum computing ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ Stochastic embeddings of graphs into trees ⋮ 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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: An approximate max-flow min-cut relation for undirected multicommodity flow, with applications