izpis_h1_title_alt

Metode sestopanja za reševanje problema podgrafnega izomorfizma
Cerk, Sven (Author), Mihelič, Jurij (Mentor) More about this mentor... This link opens in a new window, Čibej, Uroš (Co-mentor)

.pdfPDF - Presentation file, Download (1,47 MB)

Abstract
V magistrskem delu obravnavamo problem podgrafnega izomorfizma. Izhajamo iz bolj splošnega ogrodja problemov zadoščanja omejitvam. Predstavimo znane metode sestopanja za reševanje takšnih problemov in jih uporabimo pri reševanju problema podgrafnega izomorfizma. Opišemo nekaj izboljšav teh metod, pri katerih upoštevamo dodatne lastnosti obravnavanega problema. V okviru ogrodja problemov zadoščanja omejitev predstavimo tudi najuspešnejše obstoječe algoritme. Opisane metode implementiramo kot knjižnico v programskem jeziku C++. Implementacijo eksperimentalno ovrednotimo na več javno dostopnih zbirkah testnih primerov, na katerih opravimo tudi primerjavo z obstoječimi algoritmi. Osredotočimo se predvsem na primerjavo hitrosti izvajanja.

Language:Slovenian
Keywords:podgrafni izomorfizem, problemi zadoščanja omejitvam, algoritmi sestopanja, inženiring algoritmov
Work type:Master's thesis/paper (mb22)
Tipology:2.09 - Master's Thesis
Organization:FMF - Faculty of Mathematics and Physics
Year:2018
UDC:004.42
COBISS.SI-ID:18456409 Link is opened in a new window
Views:510
Downloads:224
Metadata:XML RDF-CHPDL DC-XML DC-RDF
 
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
:
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Secondary language

Language:English
Title:Backtracking methods for solving the subgraph isomorphism problem
Abstract:
The master's thesis deals with the subgraph isomorphism problem. We start by considering the more general class of constraint satisfaction problems. We present a backtracking framework for solving such problems and use it to solve the subgraph isomorphism problem. By taking into account the specific properties of our problem, we describe some improvements to the basic methods. The framework is also used to characterize some of the most successful existing algorithms. We have implemented a C++ library of the presented methods. We use it to experimentally evaluate the methods on multiple publicly available data sets and compare them with existing algorithms. The main focus of the comparison is the execution time of the algorithms.

Keywords:subgraph isomorphism, constraint satisfaction problems, backtracking algorithms

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back