In the analysis of graph data the search for an appearance of a smaller graph within a larger one is one of the more important problems. We call it the subgraph isomorphism problem. In this thesis we focus on a problem variant, where we search for the number of all induced subgraph isomorphisms on undirected graphs. We describe three related algorithms for solving this problem which we implement and then parallelize using an application programming interface called OpenMP. At parallelization we take on the approach of dynamic distribution of tasks where threads exchange tasks through a global queue. For task exchange we test our own implementation of the queue and the built-in OpenMP solution. Parallel algorithms are experimentally evaluated on two test sets. We also examine the impact of granularity on the execution time.
|
