FHNW Fachhochschule Nordwestschweiz
  • Startseite
  • Publikationen
  • Projekte
  • Studentische Arbeiten
  • de
  •  Login
Eintraganzeige 
  •   IRF Home
  • Hochschule für Wirtschaft
  • Institut für Wirtschaftsinformatik
  • Eintraganzeige
  • Hochschule für Wirtschaft
  • Institut für Wirtschaftsinformatik
  • Eintraganzeige
JavaScript is disabled for your browser. Some features of this site may not work without it.

Approximation of Graph Edit Distance in Quadratic Time

Datum
05.2015
Autorin/Autor
Riesen, Kaspar
Ferrer, Miquel
Fischer, Andreas
Bunke, Horst
Metadata
Zur Langanzeige
Type
04 - Beitrag Sammelband oder Konferenzschrift
Primary target group
Science
Created while belonging to FHNW?
Yes
Zusammenfassung
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.
URI
http://hdl.handle.net/11654/10730

Stöbern

Gesamter BestandBereiche & SammlungenErscheinungsdatumAutoren/AutorinnenTitelThemenDiese SammlungErscheinungsdatumAutoren/AutorinnenTitelThemen

Mein Benutzerkonto

EinloggenRegistrieren

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors

Kontakt

Fachhochschule Nordwestschweiz FHNW
Vizepräsidium Hochschulentwicklung
Bahnhofstrasse 6
5210 Windisch

E-Mail: irf@fhnw.ch

Über das IRF

Das IRF ist das digitale Repositorium der Fachhochschule Nordwestschweiz FHNW. Es enthält Publikationen, studentische Arbeiten und Projekte.

Links

Liste der IRF Power User
Feedbackformular

www.fhnw.ch | Impressum | Datenschutz | Urheberrecht