Exact and approximate resolution of integral multiflow and multicut problems: algorithms and complexity

This is a summary of the author’s PhD thesis supervised by Marie- Christine Costa and Frederic Roupin and defended on 20 November 2006 at the Conservatoire National des Arts et Metiers in Paris (France). The thesis is written in French and is available upon request from the author. This work deals with two well-known optimization problems from graph theory: the maximum integral multiflow and the minimum multicut problems. The main contributions of this thesis concern the polynomial-time solvability and the approximation of these two problems (and of some of their variants) in classical classes of graphs: bounded tree-width graphs, planar graphs and grids, digraphs, etc.