Project Description

Graph colouring is a theoretical problem within Graph Theory, where we seek to assign colours to the vertices of a graph so that no two vertices of the same colour are connected by an edge. Since colouring every vertex a different colour will easily achieve this, we are often interested in minimising the number of colours required. Colouring has many applications to scheduling problems for example the task of scheduling university examinations for thousands of students. Such a problem can be modeled by a graph in which there is a vertex for each exam, and two `exams' are connected by an edge precisely when there is a student that must sit both of them. A colouring of this graph then corresponds to a timetabling of the situation where no student must be in two places at once.

Graph colouring is in general an NP-complete problem, meaning there is likely to be no polynomial time algorithm to find a colouring, or to find the smallest number of colours required. However many approximate algorithms exist, which generally perform well on real world scheduling instances. The minimal aims of this project are:

  • To understand the relationship between scheduling problems and graph colourings.
  • To understand several colouring algorithms, their strengths and weaknesses.
  • To implement an agreed colouring algorithm (e.g RLF [2]) to solve scheduling instances.
To obtain high marks groups should complete one or more of the following tasks, or another agreed extension.
  • Modify the program to solve timetabling problems with additional real world constraints.
  • Modify the program to generate an html directory of individual students timetables.
It will be beneficial, though not necessary, to have taken the course 01227 Graph Theory (or to take it simultaneously).

References

[1] A Touch of Color: Graph Coloring.

[2] Frank Thomson Leighton. A graph coloring algorithm for large scheduling problems. JOURNAL OF RESEARCH of the National Bureau of Standards, 1979

Optagelsesbegrænsning: maks. 3 grupper