Doctoral course on "Algorithmic Graph Theory" by Martin Milanic

Title of course: Algorithmic Graph Theory
Lecturer:Martin Milanic
University of Primorska, Slovenia
martin DOT milanic AT upr DOT si
Level:for doctoral students
Period:5 - 9 March 2013 (Tue - Fri) and
19 - 21 March 2013 (Tue - Thu)
(exact times see below)
Contact:Zsuzsanna Lipták
zsuzsanna DOT liptak AT univr DOT it  

Here is a brief description of the course: contents.

Here are the slides of the course (all very slightly updated, 21/3/2013):

Here is a definitions handout, which you might find useful.

The course will take place in Sala Riunioni Piano Terra (Dept. of Computer Science, Ca' Vignal, 2) at the following times:
Tue 5/311.30-13.30Review of basic notions in graph theory, algorithms and complexity
Wed 6/310.30-13.30Graph colorings
Thu 7/310.30-12.30Perfect graphs and their subclasses, part 1
Fri 8/810.30-13.30Perfect graphs and their subclasses, part 2
Tue 19/310.30-13.30Further examples of tractable problems, part 1
Wed 20/310.30-13.30Further examples of tractable problems, part 2
Approximation algorithms for graph problems
Thu 21/316.30Lectio Magistralis:
“Graph classes: interrelations, structure, and algorithmic issues”
(in Sala Verde)
Participants will have the possibility of earning one credit (advanced research credit) for the course via a take-home final exam. Please register for the course, by contacting Zsuzsanna Lipták.


Graph theory is a relatively young branch of discrete mathematics that has been developing rapidly in the last decades, mostly due to its many applications in the modern world, in fields as diverse as computer science, social sciences, economics, biology and logistics. With (finite) graphs, one can model pairwise relations between entities such as computers, individuals, proteins in a cell, or cities. In their mathematical abstraction, entities are usually referred to as vertices, and the fact that that two entities are related is represented by connecting two vertices by an edge.

Among the plethora of problems that can be modeled using graphs are routing problems, traffic flow modeling, scheduling of jobs on processors, student placement, social networks, protein networks, metabolic networks, phylogeny of species, distributed communication, map drawing, Boolean circuits, to name just a few. One of the most fruitful applications of graph theory stems from its capability of modeling phenomena in static and dynamic interconnection networks. In particular, practical and theoretical issues in computer science motivate a number of graph theoretic questions and concepts, including several variants of the dominating set problem, the independent set problem, the graph coloring problem, the problems of finding either dense or sparse substructures satisfying certain connectivity requirements, or the problem of designing efficient algorithms for combinatorial optimization problems arising in the design of optical networks or other applications, and many more.

The course will give an overview of a selection of topics in structural and algorithmic graph theory. Particular emphasis will be given to algorithmic and complexity issues.