The algorithmic problem solving group conducts research into mathematical method, in particular the problemsolving skills involved in the formulation and solution of algorithmic problems. Our goal is to articulate these skills primarily by way of concrete examples, but also by the development of appropriate mathematical theory.
Written by Joao Ferreira.
 Speaker:
Jakub Marecek
 Date:
18th November 2008, from 3.00pm to 4.00pm
 Location:
C60
 Description:

The choice of a formulation of the graph colouring component determines formulations of many problems in Scheduling and Timetabling. In this talk, we first introduce the problem and briefly outline the wellknown modelling options. Next, we introduce a new formulation using the concept of “supernodes” of George and McIntyre [SIAM J. Numer. Anal. 15 (1978), no. 1, 90112]. “Supernode” is a complete subgraph, where each two vertices have the same neighbourhood outside of the subgraph. Together with a polynomialtime algorithm for obtaining the partition of an arbitrary graph into supernodes, which we give, this can be thought of as the best possible transformation of vertex colouring to vertex multicolouring, making it possible to use any formulation of vertex multicolouring to encode vertex colouring. The utility of this approach is shown on the example of Udine Course Timetabling Problem. Results of empirical tests on benchmark colouring instances from DIMACS competition, in addition to instances from timetabling applications, are provided.