Suboptimal Graph Edit Distance Based on Sorted Local Assignments

dc.accessRightsAnonymous
dc.audienceScience
dc.contributor.authorRiesen, Kaspar
dc.contributor.authorFerrer, Miquel
dc.contributor.authorBunke, Horst
dc.contributor.editorSchwenker, Friedhelm
dc.contributor.editorRoli, Fabio
dc.contributor.editorKittler, Joseph
dc.date.accessioned2015-10-08T10:08:26Z
dc.date.available2015-10-08T10:08:26Z
dc.date.issued2015
dc.description.abstractGraph 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.
dc.event.end2015-07-01
dc.event.start2015-06-29
dc.identifier.isbn978-3-319-20247-1
dc.identifier.urihttp://hdl.handle.net/11654/10150
dc.language.isoenen
dc.publisherSpringer
dc.relation.ispartofMultiple Classifier Systems - 12th International Workshop, MCS 2015, Günzburg, Germany, June 29 - July 1, 2015
dc.relation.ispartofseriesLecture Notes in Computer Science
dc.spatialHamburg
dc.titleSuboptimal Graph Edit Distance Based on Sorted Local Assignments
dc.type04B - Beitrag Konferenzschrift
dspace.entity.typePublication
fhnw.InventedHereYes
fhnw.IsStudentsWorkno
fhnw.PublishedSwitzerlandNo
fhnw.ReviewTypeAnonymous ex ante peer review of a complete publication
fhnw.affiliation.hochschuleHochschule für Wirtschaft FHNWde_CH
fhnw.affiliation.institutInstitut für Wirtschaftsinformatikde_CH
fhnw.pagination147-156
fhnw.publicationStatePublished
fhnw.seriesNumber9132
relation.isAuthorOfPublicationd761e073-1612-4d22-8521-65c01c19f97a
relation.isAuthorOfPublication811911d3-cfcd-4bb7-b1e4-aff33145b586
relation.isAuthorOfPublication.latestForDiscoveryd761e073-1612-4d22-8521-65c01c19f97a
Dateien

Lizenzbündel

Gerade angezeigt 1 - 1 von 1
Kein Vorschaubild vorhanden
Name:
license.txt
Größe:
2.94 KB
Format:
Item-specific license agreed upon to submission
Beschreibung: