Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
From MaRDI portal
Publication:685479
DOI10.1016/0020-0190(93)90228-2zbMath0803.90056OpenAlexW2062157728MaRDI QIDQ685479
Publication date: 17 October 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(93)90228-2
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)
Related Items (14)
Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover ⋮ Disjoint paths in sparse graphs ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Approximate max-flow min-multicut theorem for graphs of bounded treewidth ⋮ Correlation clustering in general weighted graphs ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ A simple algorithm for multicuts in planar graphs with outer terminals ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Integer plane multiflow maximisation: one-quarter-approximation and gaps ⋮ Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
Cites Work
This page was built for publication: Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
