A supernodal formulation of vertex colouring with applications in course timetabling

Varování

Publikace nespadá pod Ústav výpočetní techniky, 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í