magistrsko delo
Sven Cerk (Avtor), Jurij Mihelič (Mentor), Uroš Čibej (Komentor)

Povzetek

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.

Ključne besede

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

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [S. Cerk]
UDK: 004.42
COBISS: 18456409 Povezava se bo odprla v novem oknu
Št. ogledov: 1642
Št. prenosov: 445
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Backtracking methods for solving the subgraph isomorphism problem
Sekundarni povzetek: 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.
Sekundarne ključne besede: subgraph isomorphism;constraint satisfaction problems;backtracking algorithms;algorithm engineering;
Vrsta dela (COBISS): Magistrsko delo/naloga
Študijski program: 0
Konec prepovedi (OpenAIRE): 1970-01-01
Komentar na gradivo: Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Računalništvo in matematika - 2. stopnja
Strani: VII, 60 str.
ID: 10962328