Approximation of Graph Edit Distance in Quadratic Time
dc.accessRights | Anonymous | |
dc.audience | Science | |
dc.contributor.author | Riesen, Kaspar | |
dc.contributor.author | Ferrer, Miquel | |
dc.contributor.author | Fischer, Andreas | |
dc.contributor.author | Bunke, Horst | |
dc.date.accessioned | 2015-10-14T15:43:07Z | |
dc.date.available | 2015-10-14T15:43:07Z | |
dc.date.issued | 2015-05 | |
dc.description.abstract | The 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.isbn | 978-3-319-18223-0 | |
dc.identifier.uri | http://hdl.handle.net/11654/10730 | |
dc.language.iso | en | |
dc.relation.ispartof | Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. | |
dc.relation.ispartofseries | Lecture Notes in Computer Science | |
dc.spatial | Bejing | |
dc.title | Approximation of Graph Edit Distance in Quadratic Time | |
dc.type | 04B - Beitrag Konferenzschrift | |
dspace.entity.type | Publication | |
fhnw.InventedHere | Yes | |
fhnw.IsStudentsWork | no | |
fhnw.PublishedSwitzerland | No | |
fhnw.ReviewType | Anonymous ex ante peer review of a complete publication | |
fhnw.affiliation.hochschule | Hochschule für Wirtschaft | de_CH |
fhnw.affiliation.institut | Institut für Wirtschaftsinformatik | de_CH |
fhnw.publicationState | Published | |
fhnw.seriesNumber | 9069 | |
relation.isAuthorOfPublication | d761e073-1612-4d22-8521-65c01c19f97a | |
relation.isAuthorOfPublication | 811911d3-cfcd-4bb7-b1e4-aff33145b586 | |
relation.isAuthorOfPublication.latestForDiscovery | d761e073-1612-4d22-8521-65c01c19f97a |
Dateien
Lizenzbündel
1 - 1 von 1
Lade...
- Name:
- license.txt
- Größe:
- 2.94 KB
- Format:
- Item-specific license agreed upon to submission
- Beschreibung: