A NEW ALGORITHM FOR SUBGRAPH OPTIMAL ISOMORPHISM

In this paper a new algorithm for subgraph isomorphism is proposed. Th e main idea of the new algorithm is to decompose the graphs to be matc hed into smaller subgraphs. The matching process is then done at the l evel of the decomposed subgraphs based on the concept of error-correct ing 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 algor ithm is found to be O(N-4). 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. B esides, it overcomes most of the problems encountered in using tree se arch algorithms. The new algorithm is also suitable for parallelproces sing implementation. (C) 1997 Pattern Recognition Society. Published b y Elsevier Science Ltd.