Složitost a parametrizovaná složitost na dědičných třídách grafů
| Název práce v češtině: | Složitost a parametrizovaná složitost na dědičných třídách grafů |
|---|---|
| Název v anglickém jazyce: | Complexity and parameterized complexity on hereditary graph classes |
| Klíčová slova: | výpočetní složitost, parametrizovaná složitost, zakázané podgrafy |
| Klíčová slova anglicky: | computational complexity, parameterized complexity, forbidden subgraphs |
| Akademický rok vypsání: | 2018/2019 |
| Typ práce: | disertační práce |
| Jazyk práce: | |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | doc. RNDr. Jiří Fiala, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 18.09.2019 |
| Datum zadání: | 18.09.2019 |
| Datum potvrzení stud. oddělením: | 04.10.2019 |
| Zásady pro vypracování |
| Cílem práce je klasifikace výpočetní složitosti nějakého klasického problému z oblasti kombinatorické optimalizace (barevnost a její varianty, nezávislost, problémy dominance apod.) se zřetelem na třídy grafů definované pomocí jednoduchých zakázaných indukovaných podgrafů, typicky cesty či disjunktní sjednocení cest. Dle možností by charakterizace mohla být provedena vzhledem k nějakému přirozenému parametru v daném kontextu (velikost řešení, počet jednovrcholových komponent v zakázaném podgrafu apod.) |
| Seznam odborné literatury |
| R. Diestel: Graph Theory, Springer-Verlag (1997)
M. Cygan et al: Parameterized Algorithms, Springer-Verlag (2016) R. G. Downey, M. R. Fellows: Parameterized Complexity, Springer-Verlag (1999) M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman (1979) další časopisecká literatura dle doporučení školitele |