Article ID Journal Published Year Pages File Type
9663966 European Journal of Operational Research 2005 15 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, , ,