Problèmes de multicoupe et de multiflot en nombres entiers
Institution:
Paris, CNAMDisciplines:
Directors:
Abstract EN:
The object of this work is to study and to solve combinatorial optimization problems in graphs : maximum integral multiflow and minimum multicut problems, and some subproblems, as the multiterminal cut and flow, the unspittable flow, the multipath and the edge disjoint path problems are polynomial in directed trees and we propose a polynomial algorithm to solve both problems in rooted trees. We use linear programming and semi-definite programming in a branch and bound algorithm in order to solve the NP-hard minimum multicut problem in undirected trees. We propose also polynomial algorithms for the multiterminal cut and flow problems and for the minimum multicut problem in rings.
Abstract FR:
L'objet de cette thèse est l'étude et la résolution de problèmes d'optimisation combinatoire dans les graphes : les problèmes de multiflot maximal en nombres entiers et de multicoupe minimale, ainsi que de plusieurs problèmes connexes : les problèmes de coupe et flot multiterminaux, de flots inséparables, de multichemins et de chemins disjoints par les arêtes. Après avoir effectué une étude bibliographique, nous montrons que les problèmes de multiflot et de multicoupe sont polynomiaux dans les arbres orientés puis nous proposons un algorithme de séparation et d 'évaluation afin de résoudre le problème NP-difficile de la multicoupe minimale dans les arbres non orientés. Nous proposons enfin des algorithmes polynomiaux pour les problèmes de coupe et de flot multiterminaux et pour le problème de la multicoupe minimale dans les anneaux.