The maximum integer multiterminal flow problem in directed graphs

DOI10.1016/J.ORL.2006.03.005MaRDI QIDQ2643793zbMATH OpenOpenAlexFDO

Authors Cédric Bentz

Publication date 27 August 2007

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2006.03.005

zbMATH Keywords

\(APX\)-hardnessapproximation algorithmsdirected graphsinteger multiterminal flow

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Programming involving graphs or networks (90C35)

Recommendations

• The Maximum Integer Multiterminal Flow Problem
• Multi-terminal maximum flows in node-capacitated networks
• scientific article; zbMATH DE number 176254
• On multiroute maximum flows in networks.
• Combinatorial approaches to multiflow problems

Cites work

• A 2-approximation algorithm for the directed multiway cut problem
• A linear programming formulation of Mader's edge-disjoint paths problem
• A simple algorithm for the planar multiway cut problem
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• Hardness of the undirected edge-disjoint paths problem
• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• Maximal Flow Through a Network
• Minimal multicut and maximal integer multiflow: a survey
• Multiway cut and integer flow problems in trees
• Multiway cuts in directed and node weighted graphs
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Network flows. Theory, algorithms, and applications.
• On Integer Multiflow Maximization
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the disjoint paths problem
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The Complexity of Multiterminal Cuts
• The directed subgraph homeomorphism problem

Cited in

(4)

• The Maximum Integer Multiterminal Flow Problem
• An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications
• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity

This page was built for publication: The maximum integer multiterminal flow problem in directed graphs

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