## Tags : metric

Entries in this Tags : 1logs Showing : 1 - 1 / 1

## Jul 05, 2010

### Graph metric

Post @ 20:09:24 | metric

Structural pattern matching has gained a lot of attention the past decades by considering structures on features. Matching structural features thus relies on underlying graph structures.
A simple metric on graphs P and Q can be defined by

where mcs denotes the maximum common subgraph.

This bounded distance satisfies the triangle inequality property (non-trivial proof, see ref below) but is NP-hard to compute.
Nevertheless it has been used successfully in applications.

@article{graphmetric-1998,
author = {Bunke, Horst and Shearer, Kim},
title = {A graph distance metric based on the maximal common subgraph},
journal = {Pattern Recogn. Lett.},
volume = {19},
number = {3-4},
year = {1998},
issn = {0167-8655},
pages = {255--259},
doi = {http://dx.doi.org/10.1016/S0167-8655(97)00179-7},
publisher = {Elsevier Science Inc.},
address = {New York, NY, USA}
}