Graph Theory and Applications (16h)

Detailed program  

Prof.ssa Anita Pasotti
Università di Brescia

Combinatorial optimization and graph theory have experienced a fast development over the last few decades. It is well known that a lot of problems in combinatorial optimization arose directly from everyday practice in engineering and management. Indeed all the topics considered in this course are motivated by pratical interpretations. The goal is to focus on some problems of combinatorial optimization which can be formulated and treated by graph theoretical methods. After an introduction into graph theory, we study some selected topics both from a theoretical and an algorithmic point of view.
No previous knowledge of graph theory is necessary.


Monday, 18 May 2020
Preliminary concepts. Eulerian graphs. Examples of applications.

Thursday, 21 May 2020
Representations of graphs. Optimization problems.

Monday, 25 May 2020
Matching theory: definitions, properties and main theorems.

Thursday, 28 May 2020
Matching theory: algorithms and applications.

Monday, 1 June 2020
Trees and forests: definitions, properties and main theorems.

Thursday, 4 June 2020
Minimum spanning tree: algorithms.

Monday, 8 June 2020
Travelling salesman problem: basic definitions, lower bounds, approximation algorithms.

Thursday, 11 June 2020
Travelling salesman problem: upper bounds via insertion algorithms and local search.


The course will be delivered through asynchronous lessons which will be uploaded on Google Drive on the dates indicated above. Students interested are requested to contact:

Prof.ssa Anita PASOTTI
Dept. of Civil, Environmental, Architectural Engineering and Mathematics (DICATAM)