Structural and algorithmic graph theory

Ects : 3

Enseignant responsable :

Volume horaire : 15

Description 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)