Složitost a parametrizovaná složitost na dědičných třídách grafů
| Thesis title in Czech: | Složitost a parametrizovaná složitost na dědičných třídách grafů |
|---|---|
| Thesis title in English: | Complexity and parameterized complexity on hereditary graph classes |
| Key words: | výpočetní složitost, parametrizovaná složitost, zakázané podgrafy |
| English key words: | computational complexity, parameterized complexity, forbidden subgraphs |
| Academic year of topic announcement: | 2018/2019 |
| Thesis type: | dissertation |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. RNDr. Jiří Fiala, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 18.09.2019 |
| Date of assignment: | 18.09.2019 |
| Confirmed by Study dept. on: | 04.10.2019 |
| Guidelines |
| 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.) |
| References |
| 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 |