Parametrizovaná složitost v teorii grafů

• Název práce v češtině: Parametrizovaná složitost v teorii grafů
• Název v anglickém jazyce: Paramterized complexity in graph theory
• Akademický rok vypsání: 2005/2006
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. RNDr. Jan Kratochvíl, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 28.11.2005
• Datum zadání: 28.11.2005
• Datum a čas obhajoby: 11.09.2006 00:00
• Datum odevzdání elektronické podoby: 11.09.2006
• Datum odevzdání tištěné podoby: 11.09.2006
• Datum proběhlé obhajoby: 11.09.2006
• Oponenti: prof. RNDr. Daniel Kráľ, Ph.D., DSc.

Zásady pro vypracování

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í).

Seznam odborné literatury

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