Minimal multicut and maximal integer multiflow: A survey

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.

Data and Resources

Additional Info

Field Value
Source ISSN: 0377-2217
Author Costa, Marie-Christine, Létocart, Lucas, Roupin, Frédéric
Maintainer CCSD
Last Updated May 9, 2026, 22:24 (UTC)
Created May 9, 2026, 22:24 (UTC)
Identifier hal-00003243
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Centre d'études et de recherche en informatique et communications (CEDRIC) ; Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [Cnam] (Cnam)
creator Costa, Marie-Christine
date 2005-05-09T00:00:00
harvest_object_id 6983ae5d-bb93-4c1a-a665-2b21b94d242b
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-02-18T00:00:00
relation info:eu-repo/semantics/altIdentifier/doi/10.1016/j.ejor.2003.10.037
set_spec type:ART