University of Siena - Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche
June 21 h. 9-11 Room 103
June 22 h. 9-11 Room 103
June 23 h. 15-17 Room 103
June 24 h. 9-11 Room 103
June 25 h. 9-11 Room 103
June 28 h. 9-11 Room 103
June 29 h. 15-17 Room 103
June 30 h. 9-11 Room 103
July 1 h. 9-11 Room 103
July 2 h. 9-11 Room 103
In the past 20 years the application of general algebraic techniques to the solution of complexity
problems in computer science has been very fruitful.
The aim of this course is to illustrate some of these techniques (and their impact) using directed
graphs and costraint satisfaction problems (CSPs).
In particular we will try to answer the following question: when does a given (directed) graph G homomorphically map to a (directed) graph H?
For every directed graph H, this question defines a computational problem, called the "H-colouring
problem"; it is a particular instance of CSP that is helpful in understanding the general problem.