Empirično ovrednotenje reševalnikov za podgrafni izomorfizemVolk, Jana (Avtor) Čibej, Uroš (Mentor) podgrafni izomorfizemNP-polni problemireševalnikianaliza algoritmovgrafiProblem 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.20252025-09-03 14:15:01Diplomsko delo/naloga171860VisID: 38178COBISS_ID: 248581635sl