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

32 Citations (Scopus)
97 Downloads (Pure)

Abstract

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
Volume0
Issue number51
DOIs
Publication statusPublished - 1991

Keywords

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

Cite this