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. |