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

Mirjana Cangalovic; J.A.M. Schreuder

doi:10.1016/0377-2217(91)90254-S

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

Mirjana Cangalovic, J.A.M. Schreuder

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

34 Citations (Scopus)

178 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 language	Undefined
Pages (from-to)	248-258
Number of pages	11
Journal	European journal of operational research
Volume	0
Issue number	51
DOIs	https://doi.org/10.1016/0377-2217(91)90254-S
Publication status	Published - 1991

Keywords

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

Access to Document

10.1016/0377-2217(91)90254-S

Cangalovic91exact

Cite this

@article{cd5dd10a1c0f47a4b42c5f3409976b37,

title = "Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths",

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.",

keywords = "Vertex-colouring, Timetable, IR-72996, Graph, METIS-140487, Integer Programming",

author = "Mirjana Cangalovic and J.A.M. Schreuder",

year = "1991",

doi = "10.1016/0377-2217(91)90254-S",

language = "Undefined",

volume = "0",

pages = "248--258",

journal = "European journal of operational research",

issn = "0377-2217",

publisher = "Elsevier",

number = "51",

}

TY - JOUR

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

AU - Cangalovic, Mirjana

AU - Schreuder, J.A.M.

PY - 1991

Y1 - 1991

N2 - 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.

AB - 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.

KW - Vertex-colouring

KW - Timetable

KW - IR-72996

KW - Graph

KW - METIS-140487

KW - Integer Programming

U2 - 10.1016/0377-2217(91)90254-S

DO - 10.1016/0377-2217(91)90254-S

M3 - Article

SN - 0377-2217

VL - 0

SP - 248

EP - 258

JO - European journal of operational research

JF - European journal of operational research

IS - 51

ER -