A New Efficient Algorithm for Matching Weighted Graphs

摘要

In this paper a new heuristic algorithm for matching weighted graphs is proposed. The main idea of the new algorithm is to decompose the graphs to be matched into smaller subgraphs, then perform The matching process at the level of the decomposed subgraphs. 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(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 many recent methods. Besides, it overcomes most of the problems encountered in using tree search algorithms. The new algorithm is also suitable for parallel processing implementation.