Graph Optimization

The objectives of the course are: 1) to learn some polynomial time algorithms for graph optimization problems and the theoretical foundations on which these algorithms are based; 2) to implement some of the algorithms presented (a part of the course takes place in a computer lab); 3) to understand when the search for polynomial algorithms, for a new combinatorial optimization problem, is probably destined to fail (by means of the computational complexity theory).

Ability to design and implement efficient algorithms to solve polynomial complexity optimization problems on graphs.