Algoritmy založené na omezené expanzi - implementace a vyhodnocení

• Název práce v jazyce práce (slovenština): Algoritmy založené na omezené expanzi - implementace a vyhodnocení
• Název práce v češtině: Algoritmy založené na omezené expanzi - implementace a vyhodnocení
• Název v anglickém jazyce: Algorithms based on bounded expansion - implementation and evaluation
• Klíčová slova: izomorfismus podgrafů, omezená expanze, stromová dekompozice
• Klíčová slova anglicky: subgraph isomorphism, bounded expansion, tree decomposition
• Akademický rok vypsání: 2012/2013
• Typ práce: bakalářská práce
• Jazyk práce: slovenština
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 07.10.2013
• Datum zadání: 22.10.2013
• Datum potvrzení stud. oddělením: 31.10.2013
• Datum a čas obhajoby: 16.06.2014 00:00
• Datum odevzdání elektronické podoby: 23.05.2014
• Datum odevzdání tištěné podoby: 23.05.2014
• Datum proběhlé obhajoby: 16.06.2014
• Oponenti: doc. RNDr. Dušan Knop, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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