The maximum integer multiterminal flow problem in directed graphs

DOI10.1016/J.ORL.2006.03.005zbMATH Open1149.90414OpenAlexW1969477020MaRDI QIDQ2643793FDOQ2643793

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

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

zbMATH Keywords

approximation algorithmsdirected graphs\(APX\)-hardnessinteger multiterminal flow

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• The Maximum Integer Multiterminal Flow Problem
• An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications
• 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)