Výpočetní složitost v teorii grafů

• Název práce v češtině: Výpočetní složitost v teorii grafů
• Název v anglickém jazyce: Computational complexity in graph theory
• Klíčová slova: parametrizovaná složitost, Hamiltonovská cesta, barvení grafu, precoloring extension, equitable coloring
• Klíčová slova anglicky: parameterized complexity, Hamiltonian path, vertex coloring, precoloring extension, equitable coloring
• Akademický rok vypsání: 2009/2010
• 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í: 11.11.2009
• Datum zadání: 11.11.2009
• Datum a čas obhajoby: 14.05.2012 10:00
• Datum odevzdání elektronické podoby: 09.04.2012
• Datum odevzdání tištěné podoby: 10.04.2012
• Datum proběhlé obhajoby: 14.05.2012
• Oponenti: prof. Mgr. Zdeněk Dvořák, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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

Předběžná náplň práce

Uplatnění metod Fixed parameter complexity pro úlohy z teorie grafů, exaktní exponenciální algoritmy.

Předběžná náplň práce v anglickém jazyce

Application of fixed parameter complexity methods in graph theory problems, exact exponential time algorithms.