Présentation de mon domaine de recherche

Les travaux de recherche, réalisés dans le cadre de ma thèse, s'articulent autour de problématiques de routage compact et de décompositions arborescentes de graphe.  Ces travaux sont effectués, sous la direction de Cyril Gavoille au sein des équipes "Graphes et Applications" et Algorithmique Distribuée du LaBRI.

Routage compact: Le routage dans un réseau modélisé par un graphe est la donnée pour tout couple (x,y) de sommets du graphe d'une route reliant x à y. Pour la communication réelle de messages à travers un réseau chaque sommet doit calculer d'une manière locale la route d'un message qui transite par ce sommet. Ainsi le chemin se construit de manière distribuée en suivant, sommets après sommets, les chemins du routage. Le problème du routage compact consiste à trouver une description succincte de la fonction de routage qui calcule la route à suivre en chaque sommet en fonction de la destination du message. Cependant on ne peut pas parler de routage sans s’intéresser à la théorie des graphes.La théorie des graphes est un très vaste domaine; elle est en constante évolution tant du point de vue de la recherche fondamentale que celui des applications. En effet les graphes modélisent de très nombreuses situations et rendent ainsi naturel les problèmes posés. Ainsi, mes travaux de recherche dans le routage compact m'ont conduit vers des problématiques de décompositions arborescentes et de mineurs de graphe. 

Décomposition arborescente : Une des techniques couramment utilisées pour résoudre des problèmes algorithmiques sur les graphes est la décomposition de graphe. Une décomposition de graphe est une opération permettant de transformer un graphe en une structure plus simple, généralement un arbre avec éventuellement des informations sur les sommets ou les arêtes (des étiquettes). La structure arborescente de la décomposition d'un graphe permet, dans certains cas de résoudre efficacement des problèmes difficiles en général (NP-complet). De nombreux algorithmes polynomiaux utilisent d'ailleurs, explicitement ou non, des décompositions.

Mineur : Un graphe H est un mineur d'un graphe G s'il peut être obtenu en contractant les arêtes d'un sous-graphe induit de G. En d'autres termes, H peut être obtenu à partir de G en effectuant un nombre quelconque de suppression de sommets ou d'arête et/ou de contraction d'arêtes. Depuis la classification par Wagner des graphes sans mineur K5 [Wagner37], l'étude des graphes contenant (ou excluant) un certain graphe comme mineur ne cesse de passionner les chercheurs. Parmi les travaux les plus marquants, nous avons les travaux de Robertson et Seymour répartis dans une série de 23 articles.

------------------------------------------------------------------------------------------------------------------------------------

Thèse d'informatique:

• Titre: Décomposition arborescente des graphes planaires et routage compact.

• Soutenue: le 23 octobre 2009 au LaBRI-Université Bordeaux I (mention Très Honorable)

• Mots-clés:

  • distributed graph algorithms, graph algorithms

    • compact routing

    • graph minor theory

  • Composition du Jury : 

• 1. Bruno Courcelle, Professeur à l’université Bordeaux1 

     1. Pierre Fraigniaud, Directeur de Recherche à l’université Paris Diderot 

     2. Ioan Todinca, Professeur à l’université d’Orléans 

     3. André Raspaut, Professeur à l’université Bordeaux1 

     4. Cyril Gavoille, Professeur à l’université Bordeaux1 

     5. Stéphane Bessy, Maître de conférence à l’université de Montpellier 

• Rapporteurs pour la soutenance de thèse : 

• 1. Pierre Fraigniaud, Directeur de Recherche à l’université Paris Diderot 

     1.  Ioan Todinca, Professeur à l’université d’Orléans