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.

Improving bipartite graph edit distance approximation using various search strategies

Datum
04.2015
Autorin/Autor
Riesen, Kaspar
Bunke, Horst
Metadata
Zur Langanzeige
Type
01 - Zeitschriftenartikel, Journalartikel oder Magazin
Primary target group
Science
Created while belonging to FHNW?
Yes
Zusammenfassung
Recently the authors of the present paper introduced an approximation framework for the graph edit distance problem. The basic idea of this approximation is to first build a square cost matrix C=(cij)C=(cij), where each entry cij reflects the cost of a node substitution, deletion or insertion plus the matching cost arising from the local edge structure. Based on C an optimal assignment of the nodes and their local structure can be established in polynomial time. Since this approach considers local – rather than the global – structural properties of the graphs only, the graph edit distance derived from the optimal node assignment generally overestimates the true edit distance. The present paper pursues the idea of applying additional search strategies that build upon the initial assignment in order to reduce this overestimation. To this end, six different search strategies are investigated in this paper. In an exhaustive experimental evaluation on five real world graph data sets we empirically verify a substantial gain of distance accuracy by means of all search methods while run time remains remarkably low. Keywords Bipartite graph matching; Approximate graph edit distance
URI
http://hdl.handle.net/11654/10166

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