A new algorithm for subgraph optimal isomorphism

摘要

In this paper a new algorithm for subgraph isomorphism is proposed. The main idea of the new algorithm is to decompose the graphs to be matched into smaller subgraphs. The matching process is then done at the level of the decomposed subgraphs based on the concept of error-correcting transformations. The cost of matching two graphs is defined as the minimum of a weighted bipartite graph constructed from the decomposed subgraphs. The average computational complexity of the proposed algorithm is found to be O(N4). The results of the application of the new algorithm show that the new technique is quite efficient and, in many respects, superior to similar existing techniques in the literature. Besides, it overcomes most of the problems encountered in using tree search algorithms. The new algorithm is also suitable for parallel processing implementation.