hidden - assigned and confirmed by the Study Dept.
Date of registration:
11.11.2009
Date of assignment:
11.11.2009
Date and time of defence:
14.05.2012 10:00
Date of electronic submission:
09.04.2012
Date of submission of printed version:
10.04.2012
Date of proceeded defence:
14.05.2012
Opponents:
prof. Mgr. Zdeněk Dvořák, Ph.D.
Guidelines
Cílem práce je studovat algoritmické otázky teorie grafů z hlediska tzv. Fixed Parameter Complexity. Student se seznámí s touto teorií a pokusí se ji uplatnit na otevřené problémy v oblasti parametrizovatelných optimalizačních úloh na grafech. Pro dokazatelně těžké úlohy bude hledat přesné exponeciální algoritmy s cílem minimalizovat konstantu vyjadřující základ exponenciální funkce.
References
Downey, Rod; M. Fellows (1999). Parameterized complexity. Springer. ISBN 0-387-94883-X.
Niedermeier, Rolf (2006). Invitation to Fixed-Parameter Algorithms. Oxford University Press. ISBN 0-19-856607-7.
aktuální konferenční články podle zadání vedoucího
Preliminary scope of work
Uplatnění metod Fixed parameter complexity pro úlohy z teorie grafů, exaktní exponenciální algoritmy.
Preliminary scope of work in English
Application of fixed parameter complexity methods in graph theory problems, exact exponential time algorithms.
- assigned and confirmed by the Study Dept.