Problem izomorfnega podgrafa

Povzetek

Ključne besede

Podatki

Jezik:	Slovenski jezik
Leto izida:	2013
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[N. Ramovš]
UDK:	004.421.2(043.2)
COBISS:	9758036
Št. ogledov:	45
Št. prenosov:	5
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	The subgraph isomorphism problem
Sekundarni povzetek:	This thesis describes the problem of finding subgraph isomorphism. This is one of the most basic operations performed on graphs and is an NP-hard problem. We describe in detail the Ullmann algorithm and VF2 algorithm, the most commonly used and state-of-the art algorithms in this field, and a new algorithm called Subsea. We improved the VF2 algorithm using some principles from Subsea. The improvement was implemented in C++ and then compared against VF2 algorithm implementation from the program library vflib and an implementation of improved Ullmann algorithm. We tested the algorithms on a database of 9000 pairs of randomly generated graphs. In compariton to the VF2 algorithm the results show a speedup factor of at least 5 for the improved version of Ullmann algorithm and a speedup factor of at least 30 for the improved version of VF2 algorithm. The improved version of Ullmann algorithm was the fastest algorithm for small graphs, while for large graphs and graphs with many connections out improved version of VF2 algorithm proved the fastest.
Sekundarne ključne besede:	graph;subgraph;isomorphism;algorithm;computer science;diploma;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	52 str.
ID:	24181856