ECTS : 5
Volume horaire : 36
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.
Compétence à 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.