TY - CHAP
AB - Graph based pattern representation offers a number of useful properties. In particular, graphs can adapt their size and complexity to the actual pattern, and moreover, graphs are able to describe structural relations that might exist within a pattern. Yet, the high representational power and flexibility of graphs is accompanied by a significant increase of the complexity of many algorithms. For instance, exact computation of pairwise graph distance can be accomplished in exponential time complexity only. A previously introduced approximation framework reduces the problem of graph distance computation to an instance of a linear sum assignment problem. This allows suboptimal graph distance computation in cubic time. The present paper introduces a novel procedure, which is conceptually related to this previous approach, but offers O(n2log(n2)) (rather than cubic) run time. We empirically verify the speed up of our novel approximation and show that the faster approximation is able to keep up with the existing framework with respect to distance accuracy.
M3 - 04B - Beitrag Konferenzschrift
PY - 2015
DO - http://hdl.handle.net/11654/10150
A1 - Riesen, Kaspar
A1 - Ferrer, Miquel
A1 - Bunke, Horst
A2 - Schwenker, Friedhelm
A2 - Roli, Fabio
A2 - Kittler, Joseph
PB - Springer
LA - en
CY - Hamburg
VL - 9132
SN - 978-3-319-20247-
T1 - Suboptimal Graph Edit Distance Based on Sorted Local Assignments
SP - 147-156
UR - http://hdl.handle.net/11654/10150
T2 - Multiple Classifier Systems - 12th International Workshop, MCS 2015, Günzburg, Germany, June 29 - July 1, 2015
ER -