Le 09/11/2006 par bentz :

Bonjour,

j'ai le plaisir de vous inviter à la soutenance de ma thèse qui aura lieu

lundi 20 novembre 2006 à 15h en salle 35.2.25 au CNAM PARIS

ainsi qu'au pot qui suivra.

Jury :
Directeur de thèse : Marie-Christine Costa, Professeur au CNAM Paris
Co-encadrant : Frédéric Roupin, Maître de Conférences au CNAM Paris
Rapporteurs :
* Dominique de Werra, Professeur à l'EPFL, Lausanne, Suisse
* Andras Sebö, Directeur de Recherche CNRS au laboratoire Leibniz de Grenoble
Examinateurs :
* Cristina Bazgan, Professeur à l'Université Paris Dauphine
* Pascal Berthomé, Maître de Conférences à l'IUT d'Orsay
* Christophe Picouleau, Professeur au CNAM Paris

Titre : "Résolution exacte et approchée de problèmes de multiflot entier et de multicoupe : algorithmes et complexité"

Résumé :

Dans cette thèse, on s'intéresse à des problèmes de multiflot
entier et de multicoupe, qui généralisent les problèmes classiques
de flot maximum et de coupe minimum. Ces problèmes d'optimisation dans les graphes se posent notamment dans le domaine des télécommunications. Nous étudions deux aspects en particulier : la résolution exacte en temps polynomial et l'approximation polynomiale.

Nos résultats concernent différentes familles traditionnelles de graphes : anneaux, graphes orientés (avec ou sans circuits), grilles, graphes planaires et/ou de largeur d'arbre bornée...

Mots-clés : Optimisation combinatoire, Optimisation dans les graphes, Recherche Opérationnelle, Multiflots entiers, Multicoupes, Chemins disjoints, Algorithmes polynomiaux, Approximation polynomiale, NP-difficulté, APX-difficulté, Planarité, Largeur d'arbre.