Parametrizovaná složitost v teorii grafů
| Thesis title in Czech: | Parametrizovaná složitost v teorii grafů |
|---|---|
| Thesis title in English: | Paramterized complexity in graph theory |
| Academic year of topic announcement: | 2005/2006 |
| Thesis type: | diploma thesis |
| Thesis language: | čeština |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | prof. RNDr. Jan Kratochvíl, CSc. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 28.11.2005 |
| Date of assignment: | 28.11.2005 |
| Date and time of defence: | 11.09.2006 00:00 |
| Date of electronic submission: | 11.09.2006 |
| Date of submission of printed version: | 11.09.2006 |
| Date of proceeded defence: | 11.09.2006 |
| Opponents: | prof. RNDr. Daniel Kráľ, Ph.D., DSc. |
| Guidelines |
| Student nastuduje teorii parametrizované složitosti, prostuduje dostupné články o parametrizované složitosti vybraných problémů z teorie grafů (napr. nezávislost, klikovost, reprezentovatelnost jako geometrické grafy apod.) a zaměří se na zkoumání složitosti ve speciálních třídách grafů (především z hlediska geometrických reprezentací). |
| References |
| R.G. Downey, M.R. Fellows: Parametrized complexity, Springer, 1997, ISBN 0-387-94883-X
R. Downey, M. Fellows, F. Dehne: Parametrized and Exact Computation, LNCS 3162, Springer 2004, ISBN 3-540-23071-8 aktuální časopisecká literatura podle dohody s vedoucím práce |