Improved bounds for the max-flow min-multicut ratio for planar and K_r,r-free graphs

DOI10.1016/0020-0190(93)90228-2MaRDI QIDQ685479zbMATH OpenOpenAlexFDO

Authors Éva Tardos, Vijay V. Vazirani

Publication date 17 October 1993

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0020-0190(93)90228-2

zbMATH Keywords

multicommodity flow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Improved bounds on the max-flow min-cut ratio for multicommodity flows
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Approximate max-integral-flow/min-multicut theorems
• scientific article; zbMATH DE number 2086913
• A New Min‐Cut Max‐Flow Ratio for Multicommodity Flows

Cites work

• Approximate max-flow min-(multi)cut theorems and their applications
• Improved bounds on the max-flow min-cut ratio for multicommodity flows
• Multi-Commodity Network Flows

Cited in

(21)

• A simple algorithm for multicuts in planar graphs with outer terminals
• Improved bounds on the max-flow min-cut ratio for multicommodity flows
• Integer plane multiflow maximisation: one-quarter-approximation and gaps
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• Correlation clustering in general weighted graphs
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
• Approximate max-integral-flow/min-multicut theorems
• Coarse Differentiation and Multi-flows in Planar Graphs
• Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
• scientific article; zbMATH DE number 2086913 (Why is no real title available?)
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
• Approximating maximum integral multiflows on bounded genus graphs
• Approximate max-flow min-multicut theorem for graphs of bounded treewidth
• Correlation clustering for general graphs
• Minimal multicut and maximal integer multiflow: a survey
• Approximating maximum integral multiflows on bounded genus graphs
• Improved lower bounds on multiflow-multicut gaps
• Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity
• Disjoint paths in sparse graphs

This page was built for publication: Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685479)