A supernodal formulation of vertex colouring with applications in course timetabling

Edmund Burke, Jakub Mareček (), Andrew Parkes and Hana Rudová

Annals of Operations Research, 2010, vol. 179, issue 1, 105-130

Abstract: 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. Copyright Springer Science+Business Media, LLC 2010

Keywords: Vertex colouring; Graph colouring; Multicolouring; Supernode; Module; Integer programming (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-010-0716-z (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:179:y:2010:i:1:p:105-130:10.1007/s10479-010-0716-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-010-0716-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().