Structural properties of graphs and eficient algorithms: Problems Between Parameters
| Thesis title in Czech: | Strukturální vlastnosti grafů a efektivní algoritmy: Problémy separující parametry |
|---|---|
| Thesis title in English: | Structural properties of graphs and eficient algorithms: Problems Between Parameters |
| Key words: | Rozklady frafů, výpočetní složitost, parametrizovaná složitost |
| English key words: | Graph decompositions, computational complexity, parameterized complexity |
| Academic year of topic announcement: | 2011/2012 |
| Thesis type: | dissertation |
| Thesis language: | angličtina |
| 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: | 26.09.2012 |
| Date of assignment: | 26.09.2012 |
| Confirmed by Study dept. on: | 04.12.2012 |
| Date and time of defence: | 12.09.2017 15:00 |
| Date of electronic submission: | 07.06.2017 |
| Date of submission of printed version: | 28.06.2017 |
| Date of proceeded defence: | 12.09.2017 |
| Opponents: | Rolf Niedermeier |
| doc. Andreas Emil Feldmann, Dr. | |
| Guidelines |
| Cílem práce je prozkoumat možná rozšířeni Courcellovy věty, tedy různé grafové rozklady, logiky prvního a druhého řádu.
Kromě obecného případu se lze zpočátku zaměřit na specifické problémy (hledání krátkýcgh cest 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 |