Minimal multicut and maximal integer multiflow: a survey
type: Item
instance of: scholarly article
title: Minimal multicut and maximal integer multiflow: a survey
zbMATH Open document ID: 1132.90306
author: Marie-Christine Costa
author: L. Létocart
author: Frédéric Roupin
published in: European Journal of Operational Research
publication date: 2005-02-09T00:00:00Z
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 2132772
zbMATH Keywords: Integer multicommodity flows
zbMATH Keywords: Minimum multicut
zbMATH Keywords: Multiway cut
zbMATH Keywords: Complexity
zbMATH Keywords: Approximation
describes a project that uses: SDP_S
MaRDI profile type: Publication
full work available at URL: j.ejor.2003.10.037
OpenAlex ID: W2050285203
cites work: Q3056948
cites work: Q4230322
cites work: Approximation algorithms for disjoint paths and related routing and packing problems
cites work: Analysis of LP relaxations for multiway and multicut problems
cites work: A polyhedral approach to an integer multicommodity flow problem
cites work: Q4542519
cites work: On the multiway cut polyhedron
cites work: Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
cites work: Bounds and heuristics for the shortest capacitated paths problem
cites work: A greedy algorithm for multicut and integral multiflow in rooted trees
cites work: Q4035360
cites work: The Complexity of Multiterminal Cuts
cites work: On weighted multiway cuts in trees
cites work: The maximum edge-disjoint paths problem in bidirected trees
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: The directed subgraph homeomorphism problem
cites work: Q3972951
cites work: On Integer Multiflow Maximization
cites work: Multiway cuts in node weighted graphs
cites work: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
cites work: Primal-dual approximation algorithms for integral flow and multicut in trees
cites work: A Polynomial Algorithm for the k-cut Problem for Fixed k
cites work: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
cites work: Multi-Commodity Network Flows
cites work: Two-commodity cut-packing problem
cites work: Rounding algorithms for a geometric embedding of minimum multiway cut
cites work: On the Computational Complexity of Combinatorial Problems
cites work: Q4231910
cites work: Q4234048
cites work: Q4828931
cites work: A fast algorithm for maximum integral two-commodity flow in planar graphs
cites work: Multicommodity Flows in Ring Networks
cites work: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
cites work: Q4952694
cites work: On the complexity of the disjoint paths problem
cites work: A Faster Strongly Polynomial Minimum Cost Flow Algorithm
cites work: Optimization, approximation, and complexity classes
cites work: Two commodity flows
cites work: Graph minors. XIII: The disjoint paths problem
cites work: On Two Commodity Network Flows
cites work: From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems
cites work: Q3360021
cites work: Integer plane multiflows with a mixed number of demands
cites work: A two-commodity cut theorem
cites work: On complexity, representation and approximation of integral multicommodity flows
cites work: Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
DOI: 10.1016/J.EJOR.2003.10.037
description: scientific article; zbMATH DE number 2132772