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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths
scientific article

    Statements

    Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths (English)
    0 references
    0 references
    0 references
    26 June 1992
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    vertex-colouring
    0 references
    interval \(k\)-colouring
    0 references
    exact algorithm
    0 references
    interval chromatic number
    0 references
    timetabling
    0 references