Original title:
Algoritmy založené na omezené expanzi - implementace a vyhodnocení
Translated title:
Algorithms based on bounded expansion - implementation and evaluation
Authors:
Rapavá, Jana ; Dvořák, Zdeněk (advisor) ; Knop, Dušan (referee) Document type: Bachelor's theses
Year:
2014
Language:
slo Abstract:
[eng][cze] This thesis builds upon the result that a lot of graph classes - namely classes with bounded expansion - have properties which make deciding graph problems definable in first-order logic easier. One very important example of such a problem is subgraph isomorphism. The purpose of this work is to implement and test proposed algorithm for this problem (which has a linear time complexity in relation to the size of graph we are looking for the subgraph in). Powered by TCPDF (www.tcpdf.org)Tato bakalářská práce navazuje na větu, která říká, že mnoho tříd grafů - konkrétně třídy s omezenou expanzí - má vlastnosti zjednodušující rozhodování grafových problémů definovatelných v logice prvního řádu. Důležitým příkladem takového problému je izomorfismus podgrafů. Cílem této práce je implementovat a otestovat navrhnutý algoritmus pro tento problém (který má lineární časovou složitost vzhledem k velikosti grafu, ve kterém hledáme podgraf). Powered by TCPDF (www.tcpdf.org)
Keywords:
bounded expansion; bounded treedepth; subgraph isomorphism; izomorfismus podgrafů; omezená expanze; omezená stromová hloubka
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/64003