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

DOI10.1007/BF01299746MaRDI QIDQ1900189zbMATHOpenAlexFDO

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

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)

Recommendations

• A New Min‐Cut Max‐Flow Ratio for Multicommodity Flows
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• scientific article; zbMATH DE number 2086913
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• 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
• 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
• Matroids and multicommodity flows
• Multicommodity flows in planar graphs
• Packing directed circuits fractionally

Cited in

(15)

• scientific article; zbMATH DE number 2086913 (Why is no real title available?)
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• A tight max-flow min-cut duality theorem for nonlinear multicommodity flows
• On the Max-flow min-cut ratio for directed multicommodity flows
• On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths
• Hallucination helps: energy efficient virtual circuit routing
• Improved approximations for the minimum-cut ratio and the flux
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• 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
• 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
• A New Min‐Cut Max‐Flow Ratio for Multicommodity Flows

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)