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



Introduction To Algorithms Graph Theory And Parameterised Complexity


Kitty Meeks
Università di Glasgow
Course Type
Type B
September 21-25
h 10:00-12:00 17:00-19:00
Introduction to algorithmic graph theory and parameterised complexity

Kitty Meeks, University of Glasgow

Each morning session will be based around lecture-style teaching, but with significant opportunities for student interaction and discussion. The afternoon sessions will include time for students to tackle exercises individually or in small groups. Outline:

Day 1: Graphs, networks and modelling
An introduction to the basic definitions of graph theory, and an exploration of the applications of graphs and how they can be used to model a wide variety of real-world datasets

Day 2: Optimisation with graphs
Some classic optimisation problems on graphs, and algorithms to solve them – including tractable problems such as minimum spanning tree and NP-complete problems such as graph colouring.

Day 3: Classical intractability
NP-completeness in more detail, polynomial reductions, and the practical implications of NP- completeness.

Day 4: Coping with intractability
An overview of coping strategies including approximation algorithms, heuristics, and parameterised algorithms.

Day 5: Basics of parameterised complexity
Examples of NP-complete problems that admit efficient parameterised algorithms, some basic techniques in the design of such algorithms, and the notion of parameterised intractability.



PhD Students/Alumni

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