Dossier de Ignasi Sau Valls

Informations sur la thèse

Optimization in Graphs Under Degree Constraints. Application to Telecommunication Networks

Thèse de doctorat commencée le 01/10/2006 et soutenue à Sophia Antipolis, France, le 16/10/2009.

Diplôme délivré par Université de Nice - Sophia Antipolis (Nice, France) et Universitat Politècnica de Catalunya (Barcelone, Espagne). Préparé dans le(s) laboratoire(s) suivant(s) :

En France:
Projet MASCOTTE, common INRIA et I3S (CNRS et UNS). INRIA Sophia Antipolis, France.
En Espagne:
Grups de Grafs i Combinatòria, Departament de Matemàtica Aplicada 4, Universitat Politècnica de Catalunya (UPC). Barcelone, Espagne.

Sous la direction de :

En France:
Jean-Claude Bermond, DR0 CNRS.
David Coudert, CR1 INRIA.
En Espagne:
Xavier Muñoz, Associate Professor at Universitat Politècnica de Catalunya.

Thèse soutenue devant un jury composé de :

Président : Bruce Reed, McGill University, Montréal, Canada
Papporteur : David Peleg, Weizmann Institute, Rehovot, Israel
Rapporteur : Pavol Hell, Simon Fraser University, Vancouver, Canada
Membre : Jean-Claude Bermond, CNRS, Sophia Antipolis, France
Membre : David Coudert, INRIA, Sophia Antipolis, France
Membre : Miquel-Àngel Fiol, Universitat Politècnica de Catalunya, Barcelone, Espagne
Membre : Xavier Muñoz, Universitat Politècnica de Catalunya, Barcelone, Espagne

Documents associés

Résumé de la thèse

Le coeur de ces travaux de thèse fait l'objet de deux parties principales, en plus de quatre annexes correspondant à des travaux effectués en parallèle, dont la démonstration de conjectures ouvertes de longues dates.

La première partie s'intéresse au groupage de trafic, un problème fondamental dans les réseaux de télécommunications. La notion de groupage de trafic correspond à l'agrégation de flux de faible débit dans des conduits de plus gros débit. Par exemple, dans les réseaux SONET/WDM on cherchera à grouper plusieurs OC-3 (155 Mb/s) dans un même OC-48 (2.5 Gb/s) qui sera transporté par une longueur d'onde. Cependant, à chaque insertion ou extraction de trafic sur une longueur d'onde il faut placer dans le noeud du réseau un multiplexeur à insertion/extraction (ADM). De plus il faut un ADM pour chaque longueur d'onde utilisée dans le noeud, ce qui représente un coût d'équipements important. Les objectifs du groupage de trafic sont d'une part le partage efficace de la bande passante et d'autre part la réduction du coût des équipements de routage. En utilisant des outils théoriques très différents, nous répondons à des questions ouvertes et présentons des nouveaux modèles pour des scénarios dynamiques. Notamment, nous présentons des résultats d'inapproximabilité, des algorithmes d'approximation, un nouveau modèle qui permet au réseau de pouvoir router n'importe quel graphe de requêtes de degré borné, ainsi que des solutions optimales pour deux scénarios avec trafic all-to-all: l'anneau bidirectionnel et l'anneau unidirectionnel avec un facteur de groupage qui change de manière dynamique.

La deuxième partie étudie une famille de problèmes d'optimisation dans les graphes, qui peuvent être vus comme une généralisation (très large) du groupage de trafic. Il s'agit de trouver des sous-graphes dun graphe donné avec contraintes sur le degré, tout en optimisant un paramètre du graphe (très souvent, le nombre de sommets ou darêtes). Parmi les nombreux autres résultats, nous présentons des algorithmes d'approximation, des résultats d'inapproximabilité, des études sur la complexité paramétrique, des algorithmes exacts pour les graphes planaires, ainsi qu'une méthodologie générale qui permet de résoudre efficacement cette classe de problèmes (et de manière plus générale, la classe de problèmes tels qu'une solution peut être codé avec une partition d'un sous-ensemble des sommets) pour les graphes plongés dans une surface. Ce dernier résultat élargit remarquablement la classe de problèmes appelés simple-exponentiels, et implique et améliore plusieurs algorithmes existants. Pour développer cette approche, nous utilisons parmi d'autres des techniques de la théorie topologique des graphes et de combinatoire analytique. En particulier, on a étendu les structures de Catalan (qui comptent les non-crossing partitions dans les graphes planaires) pour les graphes plongés dans des surfaces arbitraires.

Finalement, plusieurs annexes présentent des résultats sur des problèmes connexes. Par exemple, nous étudions les graphes de tolérance, qui généralisent de manière naturelle les graphes d'intervalles et les graphes de permutation. Nous proposons le premier modèle d'intersection pour les graphes de tolérance généraux, donné par des parallélépipèdes en trois dimensions. Ce modèle généralise le modèle déjà connu pour les graphes de tolérance bornée, et permet d'améliorer les temps d'exécution existants pour résoudre en temps polynomial plusieurs problèmes fondamentals dans les graphes de tolérance. Nous avons aussi résolu le problème de la complexité de la reconnaissance des graphes de tolérance (qui était ouvert depuis presque 30 ans), en démontrant que reconnaître les graphes de tolérance et les graphes de tolérance bornée sont des problèmes NP-durs. Ces résultats sont surprenants, parce que les graphes de tolérance sont des graphes appelés parfaits, et la plupart de ces graphes peuvent être reconnus en temps polynomial.

Mots-clés : Théorie des graphes, groupage de trafic, réseaux optiques, décomposition de graphes, optimisation, complexité, algorithmes d'approximation, complexité paramétrée, branchwidth, programmation dynamique, graphes dans les surfaces.

En cas de problème avec ce dossier, contactez le secrétaire du prix Mathieu Giraud