A supernodal formulation of vertex colouring with applications in course timetabling

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou 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.