Théorie des Graphes avancée

This lecture is the continuation of the lecture on graphs and algorithms that I give in Master 1.

This lecture is the continuation of the lecture on graphs and algorithms that I give in Master 1 (see lecture notes). It is not crucial that you did not follow the Master 1 course as soon as you have good basis in graphs and complexity theory (but you are strongly encouraged to read and understand the lecture notes).

In this course, we will continue the study of the design of efficient algorithms. We will go further on parameterized complexity by showing some classical techniques to to design FPT algorithms (for NP-hard problems). Then, we will focus on an « easy » (polynomial) problem, namely the computation of shortest paths. This problem is at the heart of an important stream of current research on the on-line computation of itineraries. We will show how to improve the classical Dijkstra algorithm either by taking advantage of the graph structures or/and by using preprocessing.