Minimal multicut and maximal integer multiflow: a survey

DOI10.1016/j.ejor.2003.10.037zbMath1132.90306OpenAlexW2050285203MaRDI QIDQ707131

Marie-Christine Costa, Frédéric Roupin, Lucas Létocart

Publication date: 9 February 2005

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2003.10.037

zbMATH Keywords

ComplexityApproximationInteger multicommodity flowsMinimum multicutMultiway cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)

Related Items (39)

Extended cuts ⋮ On the minimum cut separator problem ⋮ The data transfer problem in a system of systems ⋮ Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions ⋮ The maximum integer multiterminal flow problem in directed graphs ⋮ Improving multicut in directed trees by upgrading nodes ⋮ A heuristic method for the minimum toll booth problem ⋮ The complexity of multicut and mixed multicut problems in (di)graphs ⋮ Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds ⋮ Algorithms for Multiterminal Cuts ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Multicut Is FPT ⋮ Multiflow Feasibility: An Annotated Tableau ⋮ Multicut in trees viewed through the eyes of vertex cover ⋮ Models and methods for solving the problem of network vulnerability ⋮ Restricted vertex multicut on permutation graphs ⋮ Unnamed Item ⋮ Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs ⋮ Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ On the complexity of the multicut problem in bounded tree-width graphs and digraphs ⋮ Finding edge-disjoint paths in networks: an ant colony optimization algorithm ⋮ How to Cut a Graph into Many Pieces ⋮ The critical node detection problem in networks: a survey ⋮ Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree ⋮ Solution methods for the vertex variant of the network system vulnerability analysis problem ⋮ A new strategy for the undirected two-commodity maximum flow problem ⋮ The multi-terminal maximum-flow network-interdiction problem ⋮ Max-multiflow/min-multicut for G+H series-parallel ⋮ Simple and improved parameterized algorithms for multiterminal cuts ⋮ On the hardness of finding near-optimal multicuts in directed acyclic graphs ⋮ The Prize-collecting Call Control Problem on Weighted Lines and Rings ⋮ Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth ⋮ Cardinality constrained and multicriteria (multi)cut problems ⋮ Multicuts and integral multiflows in rings ⋮ An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut ⋮ New results on planar and directed multicuts ⋮ Multiway cut and integer flow problems in trees

Uses Software

• SDP_S

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
• The directed subgraph homeomorphism problem
• Optimization, approximation, and complexity classes
• A two-commodity cut theorem
• A fast algorithm for maximum integral two-commodity flow in planar graphs
• Integer plane multiflows with a mixed number of demands
• Two commodity flows
• On weighted multiway cuts in trees
• From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems
• Bounds and heuristics for the shortest capacitated paths problem
• A greedy algorithm for multicut and integral multiflow in rooted trees
• Graph minors. XIII: The disjoint paths problem
• On complexity, representation and approximation of integral multicommodity flows
• A polyhedral approach to an integer multicommodity flow problem
• On the complexity of the disjoint paths problem
• The Maximum Edge-Disjoint Paths Problem in Bidirected Trees
• Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
• Rounding algorithms for a geometric embedding of minimum multiway cut
• On Integer Multiflow Maximization
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On the multiway cut polyhedron
• On the Computational Complexity of Combinatorial Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Analysis of LP relaxations for multiway and multicut problems
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The Complexity of Multiterminal Cuts
• Multiway cuts in node weighted graphs
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• On Two Commodity Network Flows
• Two-commodity cut-packing problem
• Multicommodity Flows in Ring Networks
• Multi-Commodity Network Flows
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimal multicut and maximal integer multiflow: a survey