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

 PDF - 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 podgrafni izomorfizem, problemi zadoščanja omejitvam, algoritmi sestopanja, inženiring algoritmov Master's thesis/paper (mb22) 2.09 - Master's Thesis FMF - Faculty of Mathematics and Physics 2018 004.42 18456409 510 224 (0 votes) Voting is allowed only to logged in users. AddThis uses cookies that require your consent. Edit consent...

## Secondary language

Language: English Backtracking methods for solving the subgraph isomorphism problem 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. subgraph isomorphism, constraint satisfaction problems, backtracking algorithms