Improved bounds on the max-flow min-cut ratio for multicommodity flows
From MaRDI portal
Publication:1900189
DOI10.1007/BF01299746zbMATH Open0833.68067OpenAlexW2610755752MaRDI QIDQ1900189FDOQ1900189
Authors: Serge Plotkin, Éva Tardos 
Publication date: 11 March 1996
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01299746
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Matroids and multicommodity flows
- Approximate max-flow min-(multi)cut theorems and their applications
- Approximating minimum feedback sets and multicuts in directed graphs
- Excluded minors, network decomposition, and multicommodity flow
- Packing directed circuits fractionally
- Multicommodity flows in planar graphs
- Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
- An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
- Improved approximations for the minimum-cut ratio and the flux
Cited In (15)
- Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
- An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
- Improved approximations for the minimum-cut ratio and the flux
- On the Max-flow min-cut ratio for directed multicommodity flows
- Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
- Multicommodity flows and cuts in polymatroidal networks
- Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network
- Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem
- On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths
- Title not available (Why is that?)
- A New Min‐Cut Max‐Flow Ratio for Multicommodity Flows
- Hallucination Helps: Energy Efficient Virtual Circuit Routing
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Approximate max-integral-flow/min-multicut theorems
- Coarse Differentiation and Multi-flows in Planar Graphs
This page was built for publication: Improved bounds on the max-flow min-cut ratio for multicommodity flows
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1900189)
