Minimal multicut and maximal integer multiflow: A survey

Minimal multicut and maximal integer multiflow: A survey

0.00 Avg rating0 Votes
Article ID: iaor2006326
Country: Netherlands
Volume: 162
Issue: 1
Start Page Number: 55
End Page Number: 69
Publication Date: Apr 2005
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics, programming: integer
Abstract:

We present a survey about the maximum integral multiflow and minimum multicut problems and their subproblems, such as the multiterminal cut and the unsplittable flow problems. We consider neither continuous multiflow nor minimum cost multiflow. Most of the results are very recent and some are new. We recall the dual relationship between both problems, give complexity results and algorithms, firstly in unrestricted graphs and secondly in several special graphs: trees, bipartite or planar graphs. A table summarizes the most important results.

Reviews

Required fields are marked *. Your email address will not be published.