Detailed Information on Publication Record
2010
A supernodal formulation of vertex colouring with applications in course timetabling
BURKE, K, Jakub MAREČEK, Andrew PARKES and Hana RUDOVÁBasic information
Original name
A supernodal formulation of vertex colouring with applications in course timetabling
Name in Czech
Supernodální formulace barvení vrcholů grafu s aplikacemi v rozvrhování výuky
Authors
BURKE, K (826 United Kingdom of Great Britain and Northern Ireland), Jakub MAREČEK (203 Czech Republic, guarantor, belonging to the institution), Andrew PARKES (826 United Kingdom of Great Britain and Northern Ireland) and Hana RUDOVÁ (203 Czech Republic, belonging to the institution)
Edition
Annals of Operations Research, Springer Netherlands, 2010, 0254-5330
Other information
Language
English
Type of outcome
Článek v odborném periodiku
Field of Study
10103 Statistics and probability
Country of publisher
Netherlands
Confidentiality degree
není předmětem státního či obchodního tajemství
Impact factor
Impact factor: 0.675
RIV identification code
RIV/00216224:14330/10:00043680
Organization unit
Faculty of Informatics
UT WoS
000281246700007
Keywords in English
Vertex colouring; Graph colouring; Multicolouring; Supernode; Module; Integer programming
Tags
Tags
International impact, Reviewed
Změněno: 14/12/2010 11:05, doc. Mgr. Hana Rudová, Ph.D.
V originále
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.
In Czech
Pro formulace mnoha problémů z rozvrhování v matematickém programování je důležitý výběr formulace komponenty dané barvením vrcholů grafu. V tomto článku shrnujeme známé formulace barvení vrcholů grafu a představujeme novou formulaci, založenou na "supernodes". "Supernode" je v definici George a McIntyra (SIAM J. Numer. Anal. 15(1):90-112, 1978) úplný podgraf S, ve kterém každé dva vrcholy mají shodné okolí mimo S. Rozklad na nejmenší možný počet "supernodes" je snadné získat. To nám umožňuje formulovat barvení grafu jako multi-barvení tohoto rozkladu. Pozitivní výsledky experimentů s běžně používanou kolekcí grafů (DIMACS) a řadou instancí rozvrhovacího problému (Udine Course Timetabling) jsou diskutovány.
Links
| GA201/07/0205, research and development project |
| ||
| MSM0021622419, plan (intention) |
|