A graph distance metric combining maximum common subgraph and minimum common supergraph

The relationship between two important problems in pattern recognition usin g attributed relational graphs, the maximum common subgraph and the minimum common supergraph of two graphs, is established by means of simple constru ctions, which allow to obtain the maximum common subgraph from the minimum common supergraph, and vice versa. On this basis, a new graph distance metr ic is proposed for measuring similarities between objects represented by at tributed relational graphs. The proposed metric can be computed by a straig htforward extension of any algorithm that implements error-correcting graph matching, when run under an appropriate cost function, and the extension o nly takes time linear in the size of the graphs. (C) 2001 Elsevier Science B.V. All rights reserved.