A Genetic Algorithm and its Parallelization for Graph Matching with Similarity Measures

Graph matching and similarity measures of graphs have many applications to pattern recognition, machine vision in robotics and similarity-based approximate reasoning in artificial intelligence. This paper proposes a method of matching and similarity measure between two directed labeled graphs. We define the degree of similarity, the similar correspondence and the similar map which denotes the matching between two graphs. As an approximate computing method, we apply genetic algorithms(GA) to find the similar map and compute the DS between graphs. For speed-up, we make parallel implementations on almost all steps of GA. We have implemented the sequential GA and the parallel GA in C programs and made simulations for both GAs. The simulation results show our method is efficient and useful. 1 Introduction Graph matching and similarity measure of graphs have many applications to pattern recognition, machine vision in robotics and similarity-based approximate reasoning in artificial intelli..