Informace o publikaci
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 | |
| Rok publikování | 2010 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Annals of Operations Research |
| Fakulta / Pracoviště MU | |
| 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: |