Optimalizace na grafech s omezenou stromovou šířkou přes vlastnosti vyjádřitelné v MSOL
| Thesis title in Czech: | Optimalizace na grafech s omezenou stromovou šířkou přes vlastnosti vyjádřitelné v MSOL |
|---|---|
| Thesis title in English: | Optimization in graphs with bounded treewidth |
| Key words: | Courcellova věta, stromová šířka, monadická logika druhého řádu, logické hry |
| English key words: | Courcelle's theorem, treewidth, monadic second order logic, logic games |
| Academic year of topic announcement: | 2010/2011 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. Mgr. Petr Kolman, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 22.12.2010 |
| Date of assignment: | 22.12.2010 |
| Date and time of defence: | 20.06.2011 09:00 |
| Date of electronic submission: | 26.05.2011 |
| Date of submission of printed version: | 26.05.2011 |
| Date of proceeded defence: | 20.06.2011 |
| Opponents: | prof. RNDr. Daniel Kráľ, Ph.D., DSc. |
| Guidelines |
| Klasická věta (tzv. Courcellova věta) říká, že pro každou grafovou
vlastnost vyjádřitelnou pomocí monadické logiky 2. řadu (MSOL) existuje algoritmus, který pro daný graf G rozhoduje v čase lineárním ve velikosti G, zda graf G splňuje danou vlastnost nebo ne. Věta navíc popisuje, jak z formule MSOL popisující danou vlastnost takový algoritmus získat; výsledný algoritmus žel není použitelný pro praktické použití. Courcellova věta byla později dokázána několika alternativními metodami a také byla zobecněna pro optimalizační varianty problémů (původní verze věty byla pouze pro rozhodovací problémy). Úkolem studenta bude analyzovat (případně také optimalizovat) a implementovat algoritmus plynoucí z Courcellovy věty pomocí některého z výše zmíněných alternativních důkazů; dílčím úkolem bude pokusit se o zpřehlednění či dokonce o zjednodušení důkazu. |
| References |
| Gottlob, Pichler, Wei: Monadic Datalog over Finite Structures with
Bounded Treewidth. ACM Trans. Comput. Logic 12, 1, Article 3 (November 2010) Ebinghaus, H.-D., Flum, J. Finite Model Theory. Springer; 1995. Flum, Grohe: Parametrized Complexity Theory. Springer 2006 Abiteboul, S., Hull, R., Vianu, V. Foundations of Databases. Addison-Wesley 1995 Courcelle B. The monadic second-order logic of graphs, I. Recognizable sets of finite graphs. Inf. Comput. 85, 1 (March 1990), 12-75. |