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.
|
