Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity
From MaRDI portal
Publication:926573
DOI10.1007/s10288-007-0040-xzbMath1146.90496OpenAlexW1986671061MaRDI QIDQ926573
Publication date: 20 May 2008
Published in: 4OR (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10288-007-0040-x
polynomial approximationcombinatorial optimizationmulticutsgraph theorypolynomial-time solvabilityintegral multiflows
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
- Minimal multicut and maximal integer multiflow: a survey
- The shortest multipaths problem in a capacitated dense channel
- Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
- Disjoint paths in a rectilinear grid
- Multicommodity flows in planar graphs
- Paths, flows, and VLSI-layout. Proceedings of a meeting held from June 20 to July 1, 1988, at the University of Bonn, Germany
- Efficient algorithms for \(k\)-terminal cuts on planar graphs
- A linear programming formulation of Mader's edge-disjoint paths problem
- The maximum integer multiterminal flow problem in directed graphs
- Routing through a Dense Channel with Minimum Total Wire Length
- Maximal Flow Through a Network
- Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
- The Complexity of Multiterminal Cuts
- Multiway cuts in node weighted graphs
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
