Cours d´algorithmique des graphes du MPRI

Gambette Philippe, Habib Michel

Dans de nombreux domaines tels que la chimie, la biologie, les réseaux de télécommunications ou encore les réseaux sociaux des modèles à base de graphes sont utilisés quotidiennement en recherche. De même les graphes constituent des outils importants et très utilisés de modélisation en informatique. Pour s'en convaincre il sufit de considérer la place faite aux algorithmes sur les graphes dans les ouvrages classiques d'algorithmique. En effet malgré la simplicité apparente de leur définition, les graphes capturent une large part de la complexité algorithmique. Il est donc très important de bien comprendre la structure des graphes afin d'utiliser des modélisations pertinentes à base de graphes. Ce module a deux objectifs principaux : le premier concerne la compréhension de la complexité structurelle des graphes via des décompositions de graphes et les invariants de graphes associés, tandis que le deuxième est centré sur la conception d'algorithmes "efficaces" sur les graphes et l'étude des outils algorithmiques nécessaires.