Les travaux de recherche réalisés dans le cadre de ma thèse portent principalement sur des problématiques de routage compact et de décomposition arborescente de graphes. Ils ont été menés sous la direction du Professeur Cyril Gavoille, au sein des équipes Graphes et Applications et Algorithmique Distribuée du Laboratoire Bordelais de Recherche en Informatique (LaBRI).

Routage compact

Le routage dans un réseau, modélisé par un graphe, consiste à définir, pour chaque couple de sommets (x, y), une route reliant x à y. Dans un contexte de communication réelle, chaque sommet du réseau doit être capable de déterminer localement la direction à suivre par un message qui le traverse, en fonction de sa destination. Le chemin emprunté par le message est ainsi construit de manière distribuée, sommet après sommet, conformément aux règles de routage.

Le routage compact vise alors à concevoir une description succincte de la fonction de routage, permettant à chaque sommet de calculer efficacement la prochaine étape du chemin à partir d’informations locales limitées. Cette problématique soulève des enjeux fondamentaux en termes de mémoire, de complexité et de qualité des chemins obtenus.

Ces travaux s’inscrivent naturellement dans le cadre plus général de la théorie des graphes, domaine vaste et en constante évolution, tant du point de vue de la recherche fondamentale que des applications. Les graphes constituent en effet un formalisme privilégié pour modéliser un grand nombre de systèmes réels et poser de manière naturelle des problèmes complexes. Dans ce contexte, mes recherches sur le routage compact m’ont conduit à m’intéresser plus particulièrement aux notions de décompositions arborescentes et de mineurs de graphes.

Décomposition arborescente

La décomposition de graphes est une technique couramment utilisée pour aborder des problèmes algorithmiques complexes. Elle consiste à transformer un graphe en une structure plus simple, généralement de type arborescent, éventuellement enrichie d’informations supplémentaires sur les sommets ou les arêtes.

La structure arborescente ainsi obtenue permet, dans certains cas, de résoudre efficacement des problèmes qui sont NP-complets sur des graphes généraux. De nombreux algorithmes polynomiaux exploitent d’ailleurs, explicitement ou implicitement, des décompositions arborescentes, en tirant parti de paramètres structurels tels que la largeur arborescente.

Mineurs de graphes

Un graphe H est dit mineur d’un graphe G s’il peut être obtenu à partir de G par une suite d’opérations comprenant la suppression de sommets, la suppression d’arêtes et la contraction d’arêtes. L’étude des graphes contenant — ou excluant — un graphe donné comme mineur constitue un axe majeur de la théorie des graphes.

Depuis la classification des graphes sans mineur K_5 proposée par Wagner en 1937, ce domaine n’a cessé de susciter l’intérêt des chercheurs. Parmi les contributions les plus marquantes figurent les travaux fondamentaux de Robertson et Seymour, développés dans une série remarquable de 23 articles, qui ont profondément structuré la théorie moderne des mineurs de graphes et ouvert la voie à de nombreuses applications algorithmiques.

Décrivez brièvement la culture de votre équipe.