Coordinator: Prof. Antonio Vicino
Home |  DIISM |   | Login Privacy e Cookie policy

Info

Structure




Graphs, Complexity And General Algebra

 

Prof.
Paolo Aglianò
University of Siena - Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche
Course Type
Type B
Calendar
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
Room
Program
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.





 

Courses

PhD Students/Alumni


Dip. Ingegneria dell'Informazione e Scienze Matematiche - Via Roma, 56 53100 SIENA - Italy