Graph algorithms and combinatorial optimization


Frederic GiroireNicolas NisseDavid Coudert


  • 2 ECTS

The lectures will present the basic notions of Discrete Mathematics and Combinatorial Optimization. We will focus on two important problems, namely Network Flows and their applications to connectivity, and Graph Coloring. Through these two problems, we will give the basic notions of Algorithmic, Computational Complexity and Graph Theory. During the second part of the lecture, we will present an introduction to Linear Programming and duality, revisiting Flows and Coloring Problems.

Prerequisites: basic knowledge of graph theory (shortest paths algorithms, search algorithms (BFS…)),