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.

Computing Upper and Lower Bounds of Graph Edit Distance in Cubic Time

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

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