Aspects structurels et algorithmiques dans les graphes

Crédit : 3 ECTS
Langue du cours : anglais

Le but de ce cours est de présenter plusieurs classes de graphes bien connus et de les étudier d’un point de vue structurel (théorème de caractérisation) et algorithmique.
On étudiera entre autres les classes de graphes suivants :
Graphes d’intervalles
Graphes triangulés
Graphes de permutation
Graphes de comparabilité
Graphes planaires
Graphes de largeur d’arbre bornée
Graphes parfaits
En ce qui concerne l’aspect structurel, on présentera les notions suivantes : sommet simplicial, séparateur, schéma d’élimination, triple astéroïdal, mineur, largeur d’arbre, largeur de clique, graphes d’intersection, orientation transitive, caractérisation par sous-graphes induits interdits, décomposition arborescente, k-arbre partiel, … Pour l’aspect algorithmique, on envisage d’étudier entre autres les problèmes suivants : problème de reconnaissance de ces classes de graphes, problème de coloration, problème de la clique maximum, problème du stable maximum, problème du voyageur de commerce, etc.

Bibliographie
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Second edition, Academic Press, New York, 2004, Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
A. Brandstädt, V. B. Le and J. P. Spinrad Graph Classes: A Survey SIAM Monographs on Discrete Mathematics and Applications, 1999.



Année universitaire 2019 - 2020 - Fiche modifiée le : 08-07-2019 (12H07) - Sous réserve de modification.