From exact to approximate maximum common subgraph

This paper presents an algorithm for the computation of the maximum common subgraph (MCS) between two directed, acyclic graphs with attributes. The core of the contribution resides in the modularity of the proposed algorithm which allows different heuristic techniques to be plugged in, depending on the application domain. Implemented heuristics for robust graph matching with respect to graph structural noise are discussed. As example of its effectiveness, the algortihm is applied to the problem of 3D shape similarity evaluation through structural shape descriptors.