An exact algorithm is presented for determining the interval chromatic number of a weighted graph. The algorithm is based on enumeration and the Branch-and-Bound principle. Computational experiments with the application of the algorithm to random weighted graphs are given. The algorithm and its modifications are used for solving timetabling problems with lectures of different lengths.
- Integer Programming
Cangalovic, M., & Schreuder, J. A. M. (1991). Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths. European journal of operational research, 0(51), 248-258. https://doi.org/10.1016/0377-2217(91)90254-S