The master's thesis deals with the subgraph isomorphism problem. We start by considering the more general class of constraint satisfaction problems. We present a backtracking framework for solving such problems and use it to solve the subgraph isomorphism problem. By taking into account the specific properties of our problem, we describe some improvements to the basic methods. The framework is also used to characterize some of the most successful existing algorithms.
We have implemented a C++ library of the presented methods. We use it to experimentally evaluate the methods on multiple publicly available data sets and compare them with existing algorithms. The main focus of the comparison is the execution time of the algorithms.
|
