ALGORITHMS FOR APPROXIMATE GRAPH MATCHING

Labeled graphs are graphs in which each node and edge has a label. The distance between two labeled graphs is considered to be the weighted sum of the costs of edit operations (insert, delete, and relabel the n odes and edges) to transform one graph to the other. The paper conside rs two variants of the approximate graph matching problem (AGM): Given a pattern graph P and a data graph D: 1. What is the distance between P and D? 2. What is the minimum distance between P and D when subgrap hs can be freely removed from D? We first show that no efficient algor ithm can solve either variant of the AGM unless P = NP. Then we presen t several heuristic algorithms leading to approximate solutions. The h euristics are based on probabilistic hill climbing and maximum flow te chniques. Our experimental results involving the comparison of real an d simulated data demonstrate the good performance of the algorithms pr esented.