Zur Kurzanzeige

dc.contributor.authorRiesen, Kaspar
dc.contributor.authorFerrer, Miquel
dc.contributor.authorFischer, Andreas
dc.contributor.authorBunke, Horst
dc.date.accessioned2015-10-14T15:43:07Z
dc.date.available2015-10-14T15:43:07Z
dc.date.issued2015-05
dc.identifier.isbnISBN 978-3-319-18223-0
dc.identifier.urihttp://hdl.handle.net/11654/10730
dc.description.abstractThe basic idea of a recent graph matching framework is to reduce the problem of graph edit distance (GED) to an instance of a linear sum assignment problem (LSAP). The optimal solution for this simplified GED problem can be computed in cubic time and is eventually used to derive a suboptimal solution for the original GED problem. Yet, for large scale graphs and/or large scale graph sets the cubic time complexity remains a severe handicap of this procedure. Therefore, we propose to use suboptimal algorithms – with quadratic rather than cubic time complexity – for solving the underlying LSAP. In particular, we introduce several greedy assignment algorithms for approximating GED. In an experimental evaluation we show that there is great potential for further speeding up the GED computation. Moreover, we empirically confirm that the distances obtained by this procedure remain sufficiently accurate for graph based pattern classification.
dc.language.isoen
dc.relation.ispartofGraph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015.
dc.relation.ispartofseriesLecture Notes in Computer Science 9069, Springer 2015,;
dc.accessRightsAnonymous
dc.titleApproximation of Graph Edit Distance in Quadratic Time
dc.type04 - Beitrag Sammelband oder Konferenzschrift
dc.spatialBejing
dc.audienceScience
fhnw.publicationStatePublished
fhnw.ReviewTypeAnonymous ex ante peer review of a complete publication
fhnw.InventedHereYes
fhnw.PublishedSwitzerlandNo
fhnw.IsStudentsWorkno


Dateien zu dieser Ressource

DateienGrösseFormatAnzeige

Zu diesem Eintrag gibt es keine Dateien.

Der Eintrag erscheint in:

Zur Kurzanzeige