Approximation of Graph Edit Distance in Quadratic Time

dc.accessRightsAnonymous
dc.audienceScience
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.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.identifier.isbn978-3-319-18223-0
dc.identifier.urihttp://hdl.handle.net/11654/10730
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
dc.spatialBejing
dc.titleApproximation of Graph Edit Distance in Quadratic Time
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 Wirtschaftde_CH
fhnw.affiliation.institutInstitut für Wirtschaftsinformatikde_CH
fhnw.publicationStatePublished
fhnw.seriesNumber9069
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
Lade...
Vorschaubild
Name:
license.txt
Größe:
2.94 KB
Format:
Item-specific license agreed upon to submission
Beschreibung: