| 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 |
| Tue 5/3 | 11.30-13.30 | Review of basic notions in graph theory, algorithms and complexity |
| Wed 6/3 | 10.30-13.30 | Graph colorings |
| Thu 7/3 | 10.30-12.30 | Perfect graphs and their subclasses, part 1 |
| Fri 8/8 | 10.30-13.30 | Perfect graphs and their subclasses, part 2 |
| Tue 19/3 | 10.30-13.30 | Further examples of tractable problems, part 1 |
| Wed 20/3 | 10.30-13.30 | Further examples of tractable problems, part 2 Approximation algorithms for graph problems |
| Thu 21/3 | 16.30 | Lectio Magistralis: “Graph classes: interrelations, structure, and algorithmic issues” (in Sala Verde) |
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.