2010
A supernodal formulation of vertex colouring with applications in course timetabling
BURKE, K, Jakub MAREČEK, Andrew PARKES a Hana RUDOVÁZákladní údaje
Originální název
A supernodal formulation of vertex colouring with applications in course timetabling
Název česky
Supernodální formulace barvení vrcholů grafu s aplikacemi v rozvrhování výuky
Autoři
BURKE, K (826 Velká Británie a Severní Irsko), Jakub MAREČEK (203 Česká republika, garant, domácí), Andrew PARKES (826 Velká Británie a Severní Irsko) a Hana RUDOVÁ (203 Česká republika, domácí)
Vydání
Annals of Operations Research, Springer Netherlands, 2010, 0254-5330
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10103 Statistics and probability
Stát vydavatele
Nizozemské království
Utajení
není předmětem státního či obchodního tajemství
Impakt faktor
Impact factor: 0.675
Kód RIV
RIV/00216224:14330/10:00043680
Organizační jednotka
Fakulta informatiky
UT WoS
000281246700007
Klíčová slova anglicky
Vertex colouring; Graph colouring; Multicolouring; Supernode; Module; Integer programming
Štítky
Příznaky
Mezinárodní význam, Recenzováno
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.
Česky
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.
Návaznosti
| GA201/07/0205, projekt VaV |
| ||
| MSM0021622419, záměr |
|