Výpočetní složitost problémů kombinatorické optimalizace pro specifické třídy grafů
Thesis title in Czech: | Výpočetní složitost problémů kombinatorické optimalizace pro specifické třídy grafů |
---|---|
Thesis title in English: | Computational complexity of combinatorial problems in specific graph classes |
Key words: | výpočetní složitost, kombinatorika, značkovatelnost, line-grafy |
English key words: | computational complexity, combinatorics, labeling, line graphs |
Academic year of topic announcement: | 2016/2017 |
Thesis type: | rigorosum thesis |
Thesis language: | čeština |
Department: | Department of Applied Mathematics (32-KAM) |
Supervisor: | doc. RNDr. Jiří Fiala, Ph.D. |
Author: | RNDr. Tomáš Masařík, Ph.D. - assigned and confirmed by the Study Dept. |
Date of registration: | 21.11.2016 |
Date of assignment: | 21.11.2016 |
Confirmed by Study dept. on: | 21.11.2016 |
Date and time of defence: | 08.12.2016 00:00 |
Date of electronic submission: | 21.11.2016 |
Date of submission of printed version: | 21.11.2016 |
Date of proceeded defence: | 08.12.2016 |
Guidelines |
Cílem práce je určení složitosti nějakého problému z oblasti kombinatorické optimalizace, např. L(p,q) barvení pro line grafy, nebo existence lokálně podmíněných homomorfismů pro grafy nízké stromové šířky apod. |
References |
Reinhard Diestel: Graph Theory, Springer-Verlag (1997)
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 |