Graphes

UE Complexité

Algorithmique des graphes ; notion de complexité paramétrée; résolution de problèmes par la programmation dynamique ; théorie structurelle des graphes par la largeur arborescente.

Ce cours présente les graphes et quelques paramètres classiques sur les graphes. Il présente aussi quelques familles de graphes et des algorithmes polynomiaux pour ces familles, pour des problèmes réputés difficiles.

Une deuxième partie introduira la mesure de complexité largeur arborescente et quelques techniques de programmation dynamique, avec mesure de la complexité en temps et espace dépendant de la largeur arborescente. On introduira à cet effet la complexité paramétrée ainsi que la notion de mineurs.

Une dernière partie présentera l’utilisation des graphes pour représenter des données.

Algorithmique des graphes ; notion de complexité paramétrée; résolution de problèmes par la programmation dynamique ; théorie structurelle des graphes par la largeur arborescente.