20.500.12556/RUL-171860 Empirično ovrednotenje reševalnikov za podgrafni izomorfizem Empirical evaluation of subgraph isomorphism solvers Problem podgrafnega izomorfizma je NP-poln in se pojavlja v bioinformatiki, analizi omrežij ter računalniškem vidu. V nalogi smo empirično ovrednotili pet reševalnikov induciranega podgrafnega izomorfizma: RI, VF3, PathLAD, SICS in Glasgow Subgraph Solver. Testiranje je bilo izvedeno na sintetičnih grafih (minimalna vpeta drevesa, scale-free omrežja in Erdős–Rényijevi grafi), realnih omrežjih iz zbirke SNAP ter instancah brez ujemanja. Rezultati kažejo, da se učinkovitost reševalnikov razlikuje glede na strukturo grafov in velikost vzorca: Glasgow je najboljši pri manjših in srednje velikih primerih, RI pri večjih, PathLAD pri gostih grafih, SICS pri realnih in scale-free omrežjih, VF3 pa pri redkih drevesnih strukturah. Naloga prispeva primerjalno analizo, ki raziskovalcem ponuja smernice za izbiro ustreznega reševalnika. The subgraph isomorphism problem is NP-complete and has applications in bioinformatics, network analysis, and computer vision. This thesis presents an empirical evaluation of five solvers for the induced subgraph isomorphism problem: RI, VF3, PathLAD, SICS, and the Glasgow Subgraph Solver. We tested them on synthetic graphs (minimum spanning trees, scale-free networks, and Erdős–Rényi graphs), real networks from the SNAP collection, and non-matching instances. The evaluation focused on runtime and memory usage. Results indicate that solver performance depends strongly on graph structure and pattern size: Glasgow excels on small and medium cases, RI on larger instances, PathLAD on dense graphs, SICS on real and scale-free networks, while VF3 is most effective on sparse tree-like structures. The thesis contributes a comparative analysis to guide the selection of suitable solvers for specific scenarios. podgrafni izomorfizem NP-polni problemi reševalniki analiza algoritmov grafi subgraph isomorphism NP-complete problems graph solvers algorithm analysis graphs true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2025-09-03 14:15:01 2025-09-03 14:15:07 2025-09-23 03:40:54 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 38178 248581635 Volk_Jana_-_Empiricno_ovrednotenje_resevalnikov_za_podgrafni_izomorfizem.pdf Volk_Jana_-_Empiricno_ovrednotenje_resevalnikov_za_podgrafni_izomorfizem.pdf 1 35BD430E2DEBE6380F96DB6B89C603F8 1a161b1aad6cc6a9e98780bcbba720fe8d36af87e6f1d3e56b4531176a41fa77 7c9850b9-88bf-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=215405 Fakulteta za računalništvo in informatiko 0 0 0