Algoritmy založené na omezené expanzi - implementace a vyhodnocení
| Thesis title in thesis language (Slovak): | Algoritmy založené na omezené expanzi - implementace a vyhodnocení |
|---|---|
| Thesis title in Czech: | Algoritmy založené na omezené expanzi - implementace a vyhodnocení |
| Thesis title in English: | Algorithms based on bounded expansion - implementation and evaluation |
| Key words: | izomorfismus podgrafů, omezená expanze, omezená stromová hloubka |
| English key words: | subgraph isomorphism, bounded expansion, bounded treedepth |
| Academic year of topic announcement: | 2012/2013 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | slovenština |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 07.10.2013 |
| Date of assignment: | 22.10.2013 |
| Confirmed by Study dept. on: | 04.07.2014 |
| Date and time of defence: | 04.09.2014 00:00 |
| Date of electronic submission: | 31.07.2014 |
| Date of submission of printed version: | 31.07.2014 |
| Date of proceeded defence: | 04.09.2014 |
| Opponents: | doc. RNDr. Dušan Knop, Ph.D. |
| Guidelines |
| Definice omezené expanze [NOdM1] dává jednu z možných odpovědí na otázku, co je řídký graf. Pro třídy grafů s omezenou expanzí (které zahrnují například rovinné grafy a grafy s omezeným maximálním stupněm, či obecněji třídy grafů uzavřené na podrozdělení a grafy nakreslitelné na pevnou plochu s omezeným počtem křížení na každé hraně) byly vyvinuty efektivní algoritmy a datové struktury pro problémy typu nalezení podgrafu či dominující množiny omezené velikosti [NOdM2, DKT, DK]. Tyto algoritmy lze jednoduše implementovat, není ale jasné, zda jsou prakticky využitelné (odhady na multiplikativní konstanty v jejich složitosti jsou příliš slabé).
Cílem práce je prakticky implementovat některé z těchto algoritmů, studovat jejich chování na různých třídách grafů a porovnat je s jinými existujícími algoritmy pro tyto problémy. |
| References |
| J. Nešetřil, P. Ossona de Mendez: Sparsity - Graphs, Structures, and Algorithms, Springer, 2012
[NOdM1] J. Nešetřil, P. Ossona de Mendez: Grad and classes with bounded expansion I. Decompositions. Eur. J. Comb. 29(3): 760-776 (2008) [NOdM2] J. Nešetřil, P. Ossona de Mendez: Grad and classes with bounded expansion II. Algorithmic aspects. Eur. J. Comb. 29(3): 777-791 (2008) [DKT] Z. Dvořák, D. Kráľ, R. Thomas: Deciding First-Order Properties for Sparse Graphs, FOCS 2010 [DK] A. Dawar, S. Kreutzer: Domination Problems in Nowhere-Dense Classes, FSTTCS 2009 |