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, rekonstrukce grafu, stromová šírka, hypergraf, hvezdné systémy |
| Klíčová slova anglicky: | Fixed parameter complexity, graph reconstruction, treewidth, hypergraph, star systems |
| 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í: | 04.11.2009 |
| Datum zadání: | 04.11.2009 |
| Datum a čas obhajoby: | 09.05.2011 00:00 |
| Datum odevzdání elektronické podoby: | 30.03.2011 |
| Datum odevzdání tištěné podoby: | 31.03.2011 |
| Datum proběhlé obhajoby: | 09.05.2011 |
| Oponenti: | doc. RNDr. Jiří Fiala, Ph.D. |
| Zásady pro vypracování |
| Cílem práce je studovat vybrané úlohy v teorii grafů a zkoumat jejich výpočetní složitost. Důraz bude kladen na úlohy, které jsou obtížné pro obecné grafy, jako je např. barevnost a její varianty, dominující množina, rekonstruovatelnost grafů apod. Úkolem bude snažit se nalézt polynomiální algoritmy pro speciální třídy grafů a studovat složitost vybraných problémů z hlediska teorie Fixed parameter complexity. |
| Seznam odborné literatury |
| Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4
Downey, Rod; Fellows, M. (1999), Parameterized complexity, Berlin, New York: Springer-Verlag Papadimitriou, Christos (1994). Computational Complexity (1st ed.). Addison Wesley. ISBN 0201530821 Niedermeier, Rolf (2006). Invitation to Fixed-Parameter Algorithms. Oxford University Press. ISBN 0-19-856607-7 Flum, J.; Grohe, M. (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3 sborníky konference WG - Graph Theoretical Concepts in Computer Science vydávané Springer Verlag v edici LNCS aktuální časopisecká literatura podle zadání vedoucího |
| Předběžná náplň práce |
| Studium výpočetní složitosti vybraných problémů v teorii grafů pro speciální třídy grafů a z hlediska FPT. |
| Předběžná náplň práce v anglickém jazyce |
| Study of the computational complexity of selected graph thery problems for special graph classes and from the FPT point of view. |