Minimal multicut and maximal integer multiflow: a survey

DOI10.1016/J.EJOR.2003.10.037MaRDI QIDQ707131zbMATH OpenOpenAlexFDO

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

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

ApproximationComplexityInteger multicommodity flowsMinimum multicutMultiway cut

Mathematics Subject Classification ID

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

Recommendations

• Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
• Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity
• Approximate max-integral-flow/min-multicut theorems

Cites work

• A fast algorithm for maximum integral two-commodity flow in planar graphs
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A greedy algorithm for multicut and integral multiflow in rooted trees
• A polyhedral approach to an integer multicommodity flow problem
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• A two-commodity cut theorem
• Analysis of LP relaxations for multiway and multicut problems
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximation algorithms for disjoint paths and related routing and packing problems
• Bounds and heuristics for the shortest capacitated paths problem
• From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 4211829 (Why is no real title available?)
• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• scientific article; zbMATH DE number 176254 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1261807 (Why is no real title available?)
• scientific article; zbMATH DE number 1263178 (Why is no real title available?)
• scientific article; zbMATH DE number 1775387 (Why is no real title available?)
• scientific article; zbMATH DE number 2119660 (Why is no real title available?)
• scientific article; zbMATH DE number 1445372 (Why is no real title available?)
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Integer plane multiflows with a mixed number of demands
• Multi-Commodity Network Flows
• Multicommodity Flows in Ring Networks
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Multiway cuts in node weighted graphs
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Network flows. Theory, algorithms, and applications.
• On complexity, representation and approximation of integral multicommodity flows
• On Integer Multiflow Maximization
• On the complexity of the disjoint paths problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Computational Complexity of Combinatorial Problems
• On the multiway cut polyhedron
• On Two Commodity Network Flows
• On weighted multiway cuts in trees
• Optimization, approximation, and complexity classes
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms
• The Complexity of Multiterminal Cuts
• The directed subgraph homeomorphism problem
• The maximum edge-disjoint paths problem in bidirected trees
• Two commodity flows
• Two-commodity cut-packing problem

Cited in

(43)

• Cardinality constrained and multicriteria (multi)cut problems
• Multicuts and integral multiflows in rings
• An O( n)-approximation algorithm for directed sparsest cut
• The critical node detection problem in networks: a survey
• Models and methods for solving the problem of network vulnerability
• Solution methods for the vertex variant of the network system vulnerability analysis problem
• Max-multiflow/min-multicut for G+H series-parallel
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Finding edge-disjoint paths in networks: an ant colony optimization algorithm
• The maximum integer multiterminal flow problem in directed graphs
• Improving multicut in directed trees by upgrading nodes
• Extended cuts
• The prize-collecting call control problem on weighted lines and rings
• New results on planar and directed multicuts
• On the minimum cut separator problem
• Correlation clustering with constrained cluster sizes and extended weights bounds
• Multiflow Feasibility: An Annotated Tableau
• How to Cut a Graph into Many Pieces
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• The data transfer problem in a system of systems
• Multiway cut and integer flow problems in trees
• Algorithms for Multiterminal Cuts
• The complexity of multicut and mixed multicut problems in (di)graphs
• Multicut in trees viewed through the eyes of vertex cover
• Restricted vertex multicut on permutation graphs
• Multicut Is FPT
• Multicommodity network flows: A survey. II: Solution methods
• scientific article; zbMATH DE number 7559431 (Why is no real title available?)
• Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
• Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
• A heuristic method for the minimum toll booth problem
• Approximating maximum integral multiflows on bounded genus graphs
• An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties
• A new strategy for the undirected two-commodity maximum flow problem
• The multi-terminal maximum-flow network-interdiction problem
• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• Approximating maximum integral multiflows on bounded genus graphs
• Improved parameterized and exact algorithms for cut problems on trees
• 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
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• Simple and improved parameterized algorithms for multiterminal cuts

Describes a project that uses

Uses Software

• SDP_S

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

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