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

Mirjana Cangalovic, J.A.M. Schreuder

Research output: Contribution to journalArticleAcademicpeer-review

34 Citations (Scopus)
178 Downloads (Pure)


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.
Original languageUndefined
Pages (from-to)248-258
Number of pages11
JournalEuropean journal of operational research
Issue number51
Publication statusPublished - 1991


  • Vertex-colouring
  • Timetable
  • IR-72996
  • Graph
  • METIS-140487
  • Integer Programming

Cite this