Hry na grafech ve vztahu k zdvihovým parametrům grafů
| Název práce v češtině: | Hry na grafech ve vztahu k zdvihovým parametrům grafů |
|---|---|
| Název v anglickém jazyce: | Games on graphs with respect to width parameters |
| Akademický rok vypsání: | 2007/2008 |
| Typ práce: | diplomová práce |
| Jazyk práce: | anglič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í: | 14.11.2007 |
| Datum zadání: | 14.11.2007 |
| Datum a čas obhajoby: | 22.09.2009 00:00 |
| Datum odevzdání elektronické podoby: | 22.09.2009 |
| Datum proběhlé obhajoby: | 22.09.2009 |
| Oponenti: | RNDr. Otakar Smrž, Ph.D. |
| Zásady pro vypracování |
| Student prostuduje dostupnou literaturu o hrách na grafech a zdvizích grafů (např. tree-width, branch-width, rank-width atd.) a poté se pokusí vyřešit některý otevřený problém v dané oblasti (např. existenci monotónních strategií pro některé varianty prohledávacích her apod.). |
| Seznam odborné literatury |
| Hans L. Bodlaender: A Tourist Guide through Treewidth. Acta Cybern. 11(1-2): 1-22 (1993)
Bodlaender, Hans L. (1996), "A linear time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing 25 (6): 1305?1317 Ton Kloks: Treewidth, Computations and Approximations Springer 1994 Seymour, Paul D. & Thomas, Robin, "Graph Searching and a Min-Max Theorem for Tree-Width.", Journal of Combinatorial Theory, Series B 58 (1): 22?33 Thorup, Mikkel (1998), "All structured programs have small tree width and good register allocation", Information and Computation 142 (2): 159?181 a další časopisecká literatura podle zadání vedoucího |
| Předběžná náplň práce |
| Prohledávací hry na grafech byly původně studovány vzhledem ke své praktické motivaci, později se ukázaly překvapivé souvislosti s různými parametry zdvihu grafů. V poslední době je tomuto tématu věnováno mnoho místa na informatických konferencích a specializovaných workshopech, přesto řada otázek zůstává otevřených. Především takové otázky budou ve středu zájmu a zkoumání. |
| Předběžná náplň práce v anglickém jazyce |
| Graph searching games were originally studied for their practical motivation and applications, but later a striking relationship to width parameters of graphs was discovered. In the recent zears, a lot of time is reserved for this research at international computer cience conferences and workshops, but despite of that many basic problems remain open. Mainly such problems will be in the center of interest and research in this project. |