Hry na grafech ve vztahu k zdvihovým parametrům grafů

• Thesis title in Czech: Hry na grafech ve vztahu k zdvihovým parametrům grafů
• Thesis title in English: Games on graphs with respect to width parameters
• Academic year of topic announcement: 2007/2008
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: prof. RNDr. Jan Kratochvíl, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 14.11.2007
• Date of assignment: 14.11.2007
• Date and time of defence: 22.09.2009 00:00
• Date of electronic submission: 22.09.2009
• Date of proceeded defence: 22.09.2009
• Opponents: RNDr. Otakar Smrž, Ph.D.

Guidelines

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

References

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

Preliminary scope of work

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

Preliminary scope of work in English

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.