Zur Kurzanzeige

dc.contributor.authorRiesen, Kaspar
dc.contributor.authorFischer, Andreas
dc.contributor.authorBunke, Horst
dc.contributor.editorEl Gayar, Neamat
dc.contributor.editorSchwenker, Friedhelm
dc.contributor.editorSuen, Cheng
dc.date.accessioned2015-10-05T06:30:42Z
dc.date.available2015-10-05T06:30:42Z
dc.date.issued2014
dc.identifier.isbnISBN 978-3-319-11655-6
dc.identifier.urihttp://hdl.handle.net/11654/8222
dc.description.abstractExact computation of graph edit distance (GED) can be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, since this approach considers local – rather than the global – structural properties of the graphs only, the GED derived from the optimal assignment is suboptimal. The contribution of the present paper is twofold. First, we give a formal proof that this approximation builds an upper bound of the true graph edit distance. Second, we show how the existing approximation framework can be reformulated such that a lower bound of the edit distance can be additionally derived. Both bounds are simultaneously computed in cubic time.
dc.language.isoen
dc.publisherSpringer
dc.relation.ispartofArtificial Neural Networks in Pattern Recognition - 6th IAPR TC 3 International Workshop, ANNPR 2014, Montreal, QC, Canada, October 6-8, 2014. Proceedings
dc.relation.ispartofseriesLecture Notes in Computer Science 8774, Springer 2014,;
dc.accessRightsAnonymous
dc.subject.ddc300 - Sozialwissenschaftende
dc.titleComputing Upper and Lower Bounds of Graph Edit Distance in Cubic Time
dc.type04 - Beitrag Sammelband oder Konferenzschrift
dc.spatialHamburg
dc.audienceScience
fhnw.publicationStatePublished
fhnw.ReviewTypeAnonymous ex ante peer review of a complete publication
fhnw.InventedHereYes
fhnw.PublishedSwitzerlandNo
fhnw.pagination129-140
fhnw.IsStudentsWorkno


Dateien zu dieser Ressource

DateienGrösseFormatAnzeige

Zu diesem Eintrag gibt es keine Dateien.

Der Eintrag erscheint in:

Zur Kurzanzeige