magistrsko delo
Sven Cerk (Author), Jurij Mihelič (Mentor), Uroš Čibej (Co-mentor)

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.

Keywords

podgrafni izomorfizem;problemi zadoščanja omejitvam;algoritmi sestopanja;inženiring algoritmov;

Data

Language: Slovenian
Year of publishing:
Typology: 2.09 - Master's Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [S. Cerk]
UDC: 004.42
COBISS: 18456409 Link will open in a new window
Views: 1642
Downloads: 445
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Backtracking methods for solving the subgraph isomorphism problem
Secondary 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.
Secondary keywords: subgraph isomorphism;constraint satisfaction problems;backtracking algorithms;algorithm engineering;
Type (COBISS): Master's thesis/paper
Study programme: 0
Embargo end date (OpenAIRE): 1970-01-01
Thesis comment: Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Računalništvo in matematika - 2. stopnja
Pages: VII, 60 str.
ID: 10962328