Suboptimal Graph Edit Distance Based on Sorted Local Assignments
Loading...
Authors
Author (Corporation)
Publication date
2015
Typ of student thesis
Course of study
Collections
Type
04B - Conference paper
Editors
Schwenker, Friedhelm
Roli, Fabio
Kittler, Joseph
Editor (Corporation)
Supervisor
Parent work
Multiple Classifier Systems - 12th International Workshop, MCS 2015, Günzburg, Germany, June 29 - July 1, 2015
Special issue
DOI of the original publication
Link
Series
Lecture Notes in Computer Science
Series number
9132
Volume
Issue / Number
Pages / Duration
147-156
Patent number
Publisher / Publishing institution
Springer
Place of publication / Event location
Hamburg
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
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.
Keywords
Subject (DDC)
Event
Exhibition start date
Exhibition end date
Conference start date
29.06.2015
Conference end date
01.07.2015
Date of the last check
ISBN
978-3-319-20247-1
ISSN
Language
English
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Published
Review
Peer review of the complete publication
Open access category
License
Citation
Riesen, K., Ferrer, M., & Bunke, H. (2015). Suboptimal Graph Edit Distance Based on Sorted Local Assignments. In F. Schwenker, F. Roli, & J. Kittler (Eds.), Multiple Classifier Systems - 12th International Workshop, MCS 2015, Günzburg, Germany, June 29 - July 1, 2015 (pp. 147–156). Springer. http://hdl.handle.net/11654/10150