Název: Algoritmy založené na omezené expanzi - implementace a vyhodnocení
Překlad názvu: Algorithms based on bounded expansion - implementation and evaluation
Autoři: Rapavá, Jana ; Dvořák, Zdeněk (vedoucí práce) ; Knop, Dušan (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2014
Jazyk: slo
Abstrakt: [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)
Klíčová slova: izomorfismus podgrafů; omezená expanze; stromová dekompozice; bounded expansion; subgraph isomorphism; tree decomposition

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/71520

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-340646


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce