A Graph-Decomposition Algorithm for Graph Optimal Monomorphism
Yasser El-Sonbaty
M. A. Ismail
Dept. Elec & Computer Eng
Dept. Computer Science
Arab Academy for Science and Technology
Faculty of Engineering
Alexandria 1029
Alexandria 21544
Egypt
Egypt
In this paper, a new heuristic algorithm for graph monomerism 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(N 4 ) which is better than many similar existing techniques.
A PostScript version of this paper is available.