20.500.12556/RUL-170625 Uporaba Schreier-Simsovega algoritma za učinkovitejše računanje preiskovalne ekvivalence Using the Schreier-Sims algorithm for a more efficient computation of exploratory equivalence Za problem iskanja podgrafnega izomorfizma obstaja mnogo algoritmov, a le redki vključujejo uporabo simetrij iskanega grafa za optimizacijo iskanja. To je motiviralo definicijo preiskovalne ekvivalence, ki omogoča zmanjšanje iskalnega prostora z upoštevanjem simetrij grafa, vendar pa obstoječe metode za iskanje preiskovalno ekvivalentnih particij grupo simetrij grafa in njene podgrupe obdelujejo v eksplicitni predstavitvi, kar ni najbolj učinkovito. V tem diplomskem delu bomo predstavili rezultate in algoritme iz računske teorije grup, ki nam omogočajo prilagoditev obstoječih pristopov za bolj učinkovito delo z grupami. Eden izmed ključnih obravnavanih algoritmov je Schreier-Simsov algoritem. Opisali bomo, kako lahko obravnavane koncepte uporabimo za računanje struktur, ključnih za preiskovalno ekvivalenco, kot sta stabilizator in pokritje s permutacijami. Predstavili bomo tudi novo metodo računanja pokritja s permutacijami. Svoj prilagojen postopek za iskanje preiskovalno ekvivalentnih particij bomo primerjali z obstoječim postopkom na dveh družinah zelo simetričnih grafov in pokazali, da naš pristop bistveno zmanjša prostorsko zahtevnost algoritma. There exist many algorithms for the problem of subgraph isomorphism search, but only few utilize the symmetries of the pattern graph to optimize the search. This led to the definition of exploratory equivalence, which can be used to shrink the search space by taking advantage of symmetries. However, existing methods for finding exploratory equivalent partitions work with the graph’s group of symmetries in explicit form, which is inefficient. In this thesis, we present the results and algorithms of computational group theory that enable us to extend the existing methods to handle groups more efficiently. One of the key algorithms that we cover is the Schreier-Sims algorithm. We describe how these concepts can be used to compute structures integral to exploratory equivalence, such as stabilizers and permutation covers. For the latter, we also present a novel method of computation. We compare our improvement of the existing method to the original approach on two families of highly symmetric graphs and show that our approach greatly reduces the space complexity of the algorithm. Schreier-Simsov algoritem teorija grup teorija grafov generatorji stabilizator pokritje simetrije Schreier-Sims algorithm group theory graph theory genera- tors stabilizer cover symmetries true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2025-07-10 13:35:01 2025-07-10 13:35:10 2025-07-21 11:31:16 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37993 243198467 Sikosek_Lovro_-_Uporaba_Schreier-Simsovega_algoritma_za_ucinkovitejse_racunanje_preiskovalne_ekv.pdf Sikosek_Lovro_-_Uporaba_Schreier-Simsovega_algoritma_za_ucinkovitejse_racunanje_preiskovalne_ekv.pdf 1 7AB2BBCE69BD7544DAEC8B367869A212 e59a09ed7f8587066f79993beeee87a9a88ddc198329e5ef90f131fcc070d122 056c5cce-5d80-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=212660 Fakulteta za računalništvo in informatiko 0 0 0