A First Step Towards Exact Graph Edit Distance Using Bipartite Graph Matching
Vorschaubild nicht verfügbar
Autor:innen
Autor:in (Körperschaft)
Publikationsdatum
2015
Typ der Arbeit
Studiengang
Typ
04B - Beitrag Konferenzschrift
Herausgeber:innen
Liu, Cheng-Lin
Luo, Bin
Kropatsch, Walter G.
Cheng, Yian
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015.
Themenheft
DOI der Originalpublikation
Link
Reihe / Serie
Lecture Notes in Computer Science
Reihennummer
9069
Jahrgang / Band
Ausgabe / Nummer
Seiten / Dauer
77-86
Patentnummer
Verlag / Herausgebende Institution
Springer
Verlagsort / Veranstaltungsort
Hamburg
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
In recent years, a powerful approximation framework for graph edit distance computation has been introduced. This particular approximation is based on an optimal assignment of local graph structures which can be established in polynomial time. However, as this approach considers the local structural properties of the graphs only, it yields sub-optimal solutions that overestimate the true edit distance in general. Recently, several attempts for reducing this overestimation have been made. The present paper is a starting point towards the study of sophisticated heuristics that can be integrated in these reduction strategies. These heuristics aim at further improving the overall distance quality while keeping the low computation time of the approximation framework. We propose an iterative version of one of the existing improvement strategies. An experimental evaluation clearly shows that there is large space for further substantial reductions of the overestimation in the existing approximation Framework.
Schlagwörter
Fachgebiet (DDC)
Veranstaltung
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
Enddatum der Konferenz
Datum der letzten Prüfung
ISBN
978-3-319-18223-0
ISSN
Sprache
Englisch
Während FHNW Zugehörigkeit erstellt
Ja
Publikationsstatus
Veröffentlicht
Begutachtung
Peer-Review der ganzen Publikation
Open Access-Status
Lizenz
Zitation
FERRER, Miquel, Francesco SERRATOSA und Kaspar RIESEN, 2015. A First Step Towards Exact Graph Edit Distance Using Bipartite Graph Matching. In: Cheng-Lin LIU, Bin LUO, Walter G. KROPATSCH und Yian CHENG (Hrsg.), Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015. Hamburg: Springer. 2015. S. 77–86. Lecture Notes in Computer Science, 9069. ISBN 978-3-319-18223-0. Verfügbar unter: http://hdl.handle.net/11654/8237