## 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. - 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.
- Modify the program to solve timetabling problems with additional real world constraints.
- Modify the program to generate an html directory of individual students timetables.
## 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 |