A supernodal formulation of vertex colouring with applications in course timetabling

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Supernodální formulace barvení vrcholů grafu s aplikacemi v rozvrhování výuky
Autoři	BURKE K MAREČEK Jakub PARKES Andrew RUDOVÁ Hana
Rok publikování	2010
Druh	Článek v odborném periodiku
Časopis / Zdroj	Annals of Operations Research
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	DOI pre-print
Obor	Aplikovaná statistika, operační výzkum
Klíčová slova	Vertex colouring; Graph colouring; Multicolouring; Supernode; Module; Integer programming
Popis	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.
Související projekty:	Vysoce paralelní a distribuované výpočetní systémy Dynamické aspekty rozvrhování