Graph algorithms and combinatorial optimization
Frederic Giroire, Nicolas Nisse, David 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…)),