There is a rich interplay between graph theory and the algorithmic approaches to a wide variety of combinatorial optimization problems. This applications-oriented course will explore a number of real-world problems that make use of that interplay.  The types of problems to be studied will range from those that yield to efficient exact algorithms to those that call for the design and effective use of heuristics.

The first part of the course will be an introduction to graph theory foundations, including basic definitions, models, and key results.  The introduction will be accompanied by an examination of some of the classic optimization problems, both past and present.  

The primary focus for the second part of the course will be on the design and analysis of various graph-coloring models for scheduling and timetabling problems.  Students will see how an understanding of the structural properties of a particular graph model can guide the algorithmic approaches to graph coloring, including the use of metaheuristics.

Hours 9 a.m. to noon each day

Place KU Leuven, KULAK, E. Sabbelaan 53, 8500 Kortrijk

Evaluation  will be based on one of the following two options:

 A study of one or a few papers in graph coloring followed by a 20- or 30-minute presentation summarizing the results and proposing possible directions for follow-up research

Course Outline

 1.     Definitions, terminology, and some key results in graph theory.

 2.     Models and applications:  some or all of the following seven topics are likely to be covered, and a few others may be included, depending on the background and research interests of the participants.

a.     A generic tree-growing algorithm that unifies four classic algorithms.

b.     Matroids and the greedy algorithm.

c.     Eulerian and postman tours applied to software testing.

d.     Hamiltonian cycles and the Traveling Salesman Problem.

e.     Digraphs and the Critical Path Method for project scheduling.

f.      Bandwidth

g.     Domination