Suboptimal Graph Edit Distance Based on Sorted Local Assignments
Vorschaubild nicht verfügbar
Autor:innen
Autor:in (Körperschaft)
Publikationsdatum
2015
Typ der Arbeit
Studiengang
Typ
04B - Beitrag Konferenzschrift
Herausgeber:innen
Schwenker, Friedhelm
Roli, Fabio
Kittler, Joseph
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
Multiple Classifier Systems - 12th International Workshop, MCS 2015, Günzburg, Germany, June 29 - July 1, 2015
Themenheft
DOI der Originalpublikation
Link
Reihe / Serie
Lecture Notes in Computer Science
Reihennummer
9132
Jahrgang / Band
Ausgabe / Nummer
Seiten / Dauer
147-156
Patentnummer
Verlag / Herausgebende Institution
Springer
Verlagsort / Veranstaltungsort
Hamburg
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
Graph 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.
Schlagwörter
Fachgebiet (DDC)
Veranstaltung
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
29.06.2015
Enddatum der Konferenz
01.07.2015
Datum der letzten Prüfung
ISBN
978-3-319-20247-1
ISSN
Sprache
Englisch
Während FHNW Zugehörigkeit erstellt
Ja
Publikationsstatus
Veröffentlicht
Begutachtung
Peer-Review der ganzen Publikation
Open Access-Status
Lizenz
Zitation
RIESEN, Kaspar, Miquel FERRER und Horst BUNKE, 2015. Suboptimal Graph Edit Distance Based on Sorted Local Assignments. In: Friedhelm SCHWENKER, Fabio ROLI und Joseph KITTLER (Hrsg.), Multiple Classifier Systems - 12th International Workshop, MCS 2015, Günzburg, Germany, June 29 - July 1, 2015. Hamburg: Springer. 2015. S. 147–156. Lecture Notes in Computer Science, 9132. ISBN 978-3-319-20247-1. Verfügbar unter: http://hdl.handle.net/11654/10150