| BURKE, K, Jakub MAREČEK, Andrew PARKES and Hana RUDOVÁ. A supernodal formulation of vertex colouring with applications in course timetabling. Annals of Operations Research. Springer Netherlands, 2010, vol. 179, No 1, p. 105--130. ISSN 0254-5330. |
Other formats:
BibTeX
LaTeX
RIS
@article{878831,
author = {Burke, K and Mareček, Jakub and Parkes, Andrew and Rudová, Hana},
article_number = {1},
keywords = {Vertex colouring; Graph colouring; Multicolouring; Supernode; Module; Integer programming},
language = {eng},
issn = {0254-5330},
journal = {Annals of Operations Research},
title = {A supernodal formulation of vertex colouring with applications in course timetabling},
url = {http://dx.doi.org/10.1007/s10479-010-0716-z},
volume = {179},
year = {2010}
}
TY - JOUR
ID - 878831
AU - Burke, K - Mareček, Jakub - Parkes, Andrew - Rudová, Hana
PY - 2010
TI - A supernodal formulation of vertex colouring with applications in course timetabling
JF - Annals of Operations Research
VL - 179
IS - 1
SP - 105--130
EP - 105--130
PB - Springer Netherlands
SN - 02545330
KW - Vertex colouring
KW - Graph colouring
KW - Multicolouring
KW - Supernode
KW - Module
KW - Integer programming
UR - http://dx.doi.org/10.1007/s10479-010-0716-z
N2 - For many problems in scheduling and timetabling, the choice of a mathematical programming formulation is determined by the formulation of the graph colouring component. This paper briefly surveys seven known integer programming formulations of vertex colouring and introduces a new approach using "supernodes". In the definition of George and McIntyre (SIAM J. Numer. Anal. 15(1):90-112, 1978), a "supernode" is a complete subgraph, within which every pair of vertices have the same neighbourhood outside of the subgraph. A polynomial-time algorithm for obtaining the best possible partition of an arbitrary graph into supernodes is given. This makes it possible to use any formulation of vertex multicolouring to encode vertex colouring. Results of empirical tests on benchmark instances in graph colouring (DIMACS) and timetabling (Udine Course Timetabling) are also provided and discussed.
ER -
BURKE, K, Jakub MAREČEK, Andrew PARKES and Hana RUDOVÁ. A supernodal formulation of vertex colouring with applications in course timetabling. \textit{Annals of Operations Research}. Springer Netherlands, 2010, vol.~179, No~1, p.~105--130. ISSN~0254-5330.
|
