Naslov diplomskega dela: Uporaba preiskovalne ekvivalence za pohitritev sodobnih algoritmov za problem podgrafnega izomorfizma

Povzetek:

Pri problemu podgrafnega izomorfizma se ukvarjamo z iskanjem pojavitev
podanega vzorčnega grafa v podanem tarčnem grafu. Gre za pomemben
problem na področju analize grafov, saj nastopa v vseh panogah, kjer nas
zanimajo vzorci v grafih, na primer v kemiji ali pri analizi socialnih omrežij.
Ker pa je problem podgrafnega izomorfizma NP-poln, so raziskave usmerjene
v iskanje algoritmov, ki dobro delujejo vsaj v večini praktičnih primerov.
Kot se izkaže, pa so mnogi od teh algoritmov neučinkoviti pri vzorčnih
grafih z velikim številom avtomorfizmov (simetrij). V diplomski nalogi bomo
pokazali, kako je mogoče obstoječe algoritme pohitriti z uporabo preiskovalne
ekvivalence, ekvivalenčne relacije na množici vozlišč grafa, ki temelji na
množici avtomorfizmov. Na podlagi preiskovalne ekvivalence vzorčnega grafa
je namreč mogoče definirati množico omejitev, s katerimi lahko zmanjšamo
nabor kandidatnih preslikav, ki jih moramo obravnavati pri iskanju primerkov
vzorčnega grafa v tarčnem grafu. Obstoječe algoritme za reševanje problema
podgrafnega izomorfizma smo nadgradili tako, da uporabljajo preiskovalno
ekvivalenco. Svoje razširitve smo na več javno dostopnih zbirkah grafov
primerjali z izhodiščnimi algoritmi. Izboljšave algoritmov smo objavili v
obliki javno dostopnega modula v okviru obstoječe knjižnice za reševanje
problema podgrafnega izomorfizma.

Mentor: doc. dr. Luka Fürst

Komisija za zagovor:​

doc. dr. Matej Guid (predsednik)

doc. dr. Luka Fürst (mentor),

izr. prof. dr. Matjaž Kukar (član). 

Prostor: Predavalnica 18