izpis_h1_title_alt

Integracija problema izomorfnega podgrafa v sistem ALGator : diplomsko delo
Remec, Peter (Avtor), Mihelič, Jurij (Mentor) Več o mentorju... Povezava se odpre v novem oknu, Dobravec, Tomaž (Komentor)

URLURL - Predstavitvena datoteka, za dostop obiščite http://eprints.fri.uni-lj.si/2910/ Povezava se odpre v novem oknu

Izvleček
V diplomskem delu obravnavamo problem podgrafnega izomorfizma in njegovo integracijo v sistem ALGator. Iskanje izomorfnih podgrafov je dandanes prisotno na večih znanstvenih področjih, zato se vseskozi pojavljajo novi algoritmi za reševanje problema. Podrobneje smo opisali Ullmannov algoritem, izboljšani Ullmannov algoritem in algoritem RI, ki je najnovejši izmed naštetih. Njihove implementacije, katere so primerne za iskanje izomorfizmov tako na usmerjenih kot neusmerjenih neoznačenih grafih, smo zaradi integracije v sistem ALGator napisali v programskem jeziku Java. Sistem je namenjen predvsem raziskovalcem na področju razvoja algoritmov, saj omogoča enostavno testiranje njihove učinkovitosti in analizo pridobljenih rezultatov. Funkcionalnosti sistema smo v praksi uporabili na izbranemu problemu. Poleg definicije problema smo v projekt v ALGator-ju vključili vse implementirane algoritme (izboljšani Ullmannov algoritem je podan v dveh različicah) in opazovali njihovo učinkovitost. Eksperiment smo izvedli na več kot 50000 različnih parih grafov. Z analizo rezultatov v ALGator-ju smo pokazali, da je algoritem RI v primerjavi z ostalimi tremi algoritmi najhitrejši. Na drugi strani se je najslabše izkazal Ullmannov algoritem, njegovi izboljšani različici pa sta se v določenih scenarijih celo približala algoritmu RI. Z integracijo problema v sistem ALGator smo predstavili njegove zmogljivosti in navedli predloge za izboljšave.

Jezik:Slovenski jezik
Ključne besede:graf, podgraf, algoritem, izomorfizem, ALGator, računalništvo, računalništvo in informatika, univerzitetni študij, diplomske naloge
Vrsta gradiva:Diplomsko delo/naloga (mb11)
Tipologija:2.11 - Diplomsko delo
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2015
Založnik:[P. Remec]
Št. strani:69 str.
UDK:004.42(043.2)
COBISS.SI-ID:1536216771 Povezava se odpre v novem oknu
Število ogledov:724
Število prenosov:189
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Integration of subgraph isomorphism problem into ALGator system
Izvleček:
This thesis deals with a subgraph isomorphism problem and its integration into ALGator system. Detection of isomorphic subgraph is present in many scientific fields nowadays, therefore new problem solving algorithms constantly appear. We focus on a detailed description of Ullmann algorithm, improved Ullmann algorithm and RI algorithm, the most recent among listed. Those algorithms, which are suitable for isomorphism detection in directed or undirected unlabeled graphs, were implemented in Java programming language for the purpose of integration into ALGator. The system is intended for the use of algorithm development researchers, providing simplified testing of algorithm's efficiency and analysis of testing results. We have applied system functionalities on the selected problem. In addition to a problem definition we have included all the implemented algorithms into ALGator project (improved Ullmann algorithm is given in two versions) and observed their efficiency. We have executed the experiment on more than 50000 different pairs of graphs. The analysis of testing results with ALGator shows, that RI algorithm is the fastest one among all four algorithms. On the other hand Ullmann algorithm performed the worst, while the performance of its improved versions were even comparable with RI algorithm in certain scenarios. By integrating the problem into ALGator we have presented its capabilities and proposed some improvements.

Ključne besede:graph, subgraph, algorithm, isomorphism, ALGator, computer science, computer and information science, diploma

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj