20.500.12556/RUL-103888 Metode sestopanja za reševanje problema podgrafnega izomorfizma magistrsko delo Backtracking methods for solving the subgraph isomorphism problem 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. 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. podgrafni izomorfizem problemi zadoščanja omejitvam algoritmi sestopanja inženiring algoritmov subgraph isomorphism constraint satisfaction problems backtracking algorithms true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2018-09-28 07:45:44 2018-09-28 07:45:48 2025-09-17 13:22:55 0000-00-00 00:00:00 2018 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.42 92617 18456409 442.pdf 442.pdf 1 85C72CC8E48572C7C2A8FFE6E64FB941 3e71477d6387719019582190edec96daeca1e048bd704beb6eefebb8dbe5702d ed9a5781-a1b5-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=114389 Fakulteta za matematiko in fiziko Fakulteta za računalništvo in informatiko 0 0 0