Graph theory

Crédit : 5 ECTS
Langue du cours : anglais

Volume horaire

• CM : 36 h
• Volume horaire global (hors stage) : 36 h

Compétences à acquérir

At the end of the course students will be familiar with the most important optimization problems on graphs and be able to distinguish several notable cases where these problems are efficiently solvable.

Description du contenu de l'enseignement

Volume horaire :
CM : 18h
TD : 18h
This class provides an introduction to Graph Theory from a computer science and algorithms perspective. Our goal will be to understand which optimization problems on graphs admit efficient (polynomial-time) algorithms and how graph structure affects algorithmic tractability. In the first half of the course, we will cover basic topics in graph theory, including problems related to connectivity and cuts (Menger's theorem), Coloring (Brooks' theorem), and Bipartite matching (Konig's theorem). The second half will focus on studying the interplay between computational complexity and graph structure by considering notable classes of graphs, including planar, chordal, interval, and split graphs. The objective will be to understand how such graph structures can arise in practice and how they can be exploited algorithmically.

Pré-requis recommandés

This class can be considered as a natural continuation of the "Graph Algorithms" course offered on the L3 level. It is recommended for students to be familiar with the contents of this (or a similar) previous course, including the basic definitions of graphs and fundamental algorithms (such as BFS, DFS). However, this course is intended to be self-contained and familiarity with these topics, though helpful, is not mandatory.

Enseignant responsable

MICHAIL LAMPIS