Computing Upper and Lower Bounds of Graph Edit Distance in Cubic Time
Autor:innen
Autor:in (Körperschaft)
Publikationsdatum
2014
Typ der Arbeit
Studiengang
Typ
04B - Beitrag Konferenzschrift
Herausgeber:innen
El Gayar, Neamat
Schwenker, Friedhelm
Suen, Cheng
Herausgeber:in (Körperschaft)
Betreuer:in
Ãœbergeordnetes Werk
Artificial Neural Networks in Pattern Recognition - 6th IAPR TC 3 International Workshop, ANNPR 2014, Montreal, QC, Canada, October 6-8, 2014. Proceedings
Themenheft
DOI der Originalausgabe
Link
Reihe / Serie
Lecture Notes in Computer Science
Jahrgang / Band
8774
Ausgabe / Nummer
Seiten / Dauer
129-140
Patentnummer
Verlag / Herausgebende Institution
Springer
Verlagsort / Veranstaltungsort
Hamburg
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
Exact computation of graph edit distance (GED) can be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, since this approach considers local – rather than the global – structural properties of the graphs only, the GED derived from the optimal assignment is suboptimal. The contribution of the present paper is twofold. First, we give a formal proof that this approximation builds an upper bound of the true graph edit distance. Second, we show how the existing approximation framework can be reformulated such that a lower bound of the edit distance can be additionally derived. Both bounds are simultaneously computed in cubic time.
Schlagwörter
Fachgebiet (DDC)
300 - Sozialwissenschaften
Veranstaltung
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
Enddatum der Konferenz
Datum der letzten Prüfung
ISBN
978-3-319-11655-6
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, Andreas FISCHER und Horst BUNKE, 2014. Computing Upper and Lower Bounds of Graph Edit Distance in Cubic Time. In: Neamat EL GAYAR, Friedhelm SCHWENKER und Cheng SUEN (Hrsg.), Artificial Neural Networks in Pattern Recognition - 6th IAPR TC 3 International Workshop, ANNPR 2014, Montreal, QC, Canada, October 6-8, 2014. Proceedings. Hamburg: Springer. 2014. Lecture Notes in Computer Science. ISBN 978-3-319-11655-6. Verfügbar unter: http://hdl.handle.net/11654/8222