A supernodal formulation of vertex colouring with applications in course timetabling

Logo poskytovatele

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
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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.