Graph-colouring Algorithms for Scheduling

A guided research project in Algorithms & Discrete Mathematics.

← Algorithms & Discrete Mathematics projects

Experience Research Algorithms & Discrete Mathematics

Question

How many time slots are needed when conflicting activities cannot occur together?

A proper graph colouring is a schedule in which every conflict is separated.
A proper graph colouring is a schedule in which every conflict is separated.

Goals

  • Convert a scheduling problem into graph colouring.
  • Compare exact and approximate colouring algorithms.

Method

Make each activity a vertex and join two vertices whenever their times must differ.

  • Build the conflict graph from the scheduling data.
  • Apply greedy, backtracking, or other colouring methods.
  • Measure the number of colours, running time, and effect of the vertex order.