Cours d´algorithmique des graphes  du MPRI

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.

Mots-clés : algorithmique,complexité,théorie des graphes,décomposition modulaire,algorithme décomposition modulaire,largeur arborescente,algorithme LexBFS,modélisation,fuscia
Type de document : texte
Type de ressource : lecture
Niveau : higher education,master,bac+5
Publics visés : learner
Activité induite : apprendre
Auteurs ou éditeurs : Philippe Gambette,Michel Habib