@Article{ fernandez.valiente:prl:2001,
author = {Mirtha-Lina Fern\'andez and Gabriel Valiente},
title = {A Graph Distance Measure Combining Maximum Common Subgraph
and Minimum Common Supergraph},
journal = {Pattern Recognition Letters},
year = 2001,
volume = 22,
number = {6--7},
pages = {753--758},
abstract = {The relationship between two important problems in pattern
recognition using attributed relational graphs, the maximum
common subgraph and the minimum common supergraph of two
graphs, is established by means of simple constructions,
which allow to obtain the maximum common subgraph from the
minimum common supergraph, and vice versa. On this basis, a
new graph distance metric is proposed for measuring
similarities between objects represented by attributed
relational graphs. The proposed metric can be computed by a
straightforward extension of any algorithm that implements
error-correcting graph matching, when run under an
appropriate cost function, and the extension only takes
time linear in the size of the graphs.}
}