Barvení grafů za použití nikdenenulových toků
| Název práce v češtině: | Barvení grafů za použití nikdenenulových toků |
|---|---|
| Název v anglickém jazyce: | Graph coloring via nowhere-zero flows |
| Akademický rok vypsání: | 2018/2019 |
| Typ práce: | projekt |
| Jazyk práce: | |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Řešitel: | skrytý - zadáno vedoucím/školitelem |
| Datum přihlášení: | 14.11.2018 |
| Datum zadání: | 14.11.2018 |
| Zásady pro vypracování |
| Dualitu mezi barvením a nikdenenulovými toky lze použít k návrhu algoritmů pro 3-barevnost rovinných grafů či grafů vnořených na jiné plochy omezeného rodu; viz například Dvořák a Lidický [DL]. Tento algoritmus je teoreticky efektivní v případě, že skoro všechny stěny uvažovaného grafu mají délku 4.
Cílem práce je implementovat takový algoritmus (alespoň pro rovinné grafy, případně např. pro projektivně rovinné grafy či grafy na toru) a vyhodnotit jeho efektivitu např. ve srovnání s optimalizovaným backtrackingem či algoritmem využívajícím existenci malých separátorů na vhodných třídách grafů (náhodné rovinné grafy dané hustoty, či grafy z nějakého benchmarku). Výsledky práce budou prezentovány formou zaslání na SVOČ. |
| Seznam odborné literatury |
| [DL] Zdeněk Dvořák, Bernard Lidický: 3-Coloring Triangle-Free Planar Graphs with a Precolored 8-Cycle. Journal of Graph Theory 80(2): 98-111 (2015)
[BT] Mohar, Bojan, and Carsten Thomassen. Graphs on surfaces. Vol. 10. JHU Press, 2001. |