Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths (Q1179200)

Let \(G=(V,E)\) be a graph associated with a weight function \(c: V\to\{1,2,3,\dots\}\). For a positive integer \(k\), an assignment of consecutive segments with distinct numbers from \(\{1,2,\dots,k\}\) in linear order to vertices such that \(c(v)=\) the length of the segment for \(v\in V\) and no more adjacent vertices are with the same segment is said to be an interval \(k\)-colouring of \(G\). This paper provides an exact algorithm for determining the interval chromatic number which is the smallest \(k\) among all interval \(k\)-colourings of \(G\) based on enumeration and the branch-and-bound principle. Further, the algorithm is used for solving the timetabling problems with lectures of different lengths.