Structural and algorithmic graph theory
Enseignant responsable :
Volume horaire : 15Description du contenu de l'enseignement :
In this course, we introduce several well-known graph classes and we study their structural properties (e.g. characterization theorems) as well as their algorithmic properties (e.g. efficient algorithms for some classical optimization problems).
Compétence à acquérir :
We study among others the following graph classes: interval graphs, chordal graphs, permutation graphs, comparability graphs, planar graphs, bounded treewidth graphs, perfect graphs. Concerning the structural properties, we will introduce for instance the following notions: simplicial vertex, separator, elimination scheme, asteroidal triple, minor, treewidth, cliquewidth, intersection graph, transitive orientation, characterization by a family of forbidden induced subgraphs, tree decomposition, partial k-tree, … . Concerning the algorithmic properties, we will focus on the following classical optimization problems: recognition problem for the graph classes mentioned above, coloring problem, maximum clique problem, maximum stable set problem, travelling salesman problem, …
Bibliographie, lectures recommandées
Bibliographie Combinatorial Optimization : Polyedra and Efficiency. A. Schrijver , Springer (2003)