Structural properties of graphs and eficient algorithms: Problems Between Parameters
| Název práce v češtině: | Strukturální vlastnosti grafů a efektivní algoritmy: Problémy separující parametry |
|---|---|
| Název v anglickém jazyce: | Structural properties of graphs and eficient algorithms: Problems Between Parameters |
| Klíčová slova: | Rozklady frafů, výpočetní složitost, parametrizovaná složitost |
| Klíčová slova anglicky: | Graph decompositions, computational complexity, parameterized complexity |
| Akademický rok vypsání: | 2011/2012 |
| Typ práce: | disertační práce |
| Jazyk práce: | angličtina |
| Ú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í: | 26.09.2012 |
| Datum zadání: | 26.09.2012 |
| Datum potvrzení stud. oddělením: | 04.12.2012 |
| Datum a čas obhajoby: | 12.09.2017 15:00 |
| Datum odevzdání elektronické podoby: | 07.06.2017 |
| Datum odevzdání tištěné podoby: | 28.06.2017 |
| Datum proběhlé obhajoby: | 12.09.2017 |
| Oponenti: | Rolf Niedermeier |
| doc. Andreas Emil Feldmann, Dr. | |
| Zásady pro vypracování |
| 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.). |
| Seznam odborné literatury |
| 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 |