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