Ferrer, Miquel

Profilbild
E-Mail-Adresse
Geburtsdatum
Projekt
Organisationseinheiten
Berufsbeschreibung
Nachname
Ferrer
Vorname
Miquel
Name
Ferrer, Miquel

Filter

20152
Filter zurücksetzen

Einstellungen

Autor:in: Bunke, Horst ×

Suchergebnisse

Gerade angezeigt 1 - 2 von 2
  • Vorschaubild nicht verfügbar
    Publikation
    Approximation of Graph Edit Distance in Quadratic Time
    (05/2015) Riesen, Kaspar; Ferrer, Miquel; Fischer, Andreas; Bunke, Horst [in: Graph-Based Representations in Pattern Recognition - 10th IAPR-TC-15 International Workshop, GbRPR 2015, Beijing, China, May 13-15, 2015.]
    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.
    04B - Beitrag Konferenzschrift
  • Vorschaubild nicht verfügbar
    Publikation
    Suboptimal Graph Edit Distance Based on Sorted Local Assignments
    (Springer, 2015) Riesen, Kaspar; Ferrer, Miquel; Bunke, Horst; Schwenker, Friedhelm; Roli, Fabio; Kittler, Joseph [in: Multiple Classifier Systems - 12th International Workshop, MCS 2015, Günzburg, Germany, June 29 - July 1, 2015]
    Graph based pattern representation offers a number of useful properties. In particular, graphs can adapt their size and complexity to the actual pattern, and moreover, graphs are able to describe structural relations that might exist within a pattern. Yet, the high representational power and flexibility of graphs is accompanied by a significant increase of the complexity of many algorithms. For instance, exact computation of pairwise graph distance can be accomplished in exponential time complexity only. A previously introduced approximation framework reduces the problem of graph distance computation to an instance of a linear sum assignment problem. This allows suboptimal graph distance computation in cubic time. The present paper introduces a novel procedure, which is conceptually related to this previous approach, but offers O(n2log(n2)) (rather than cubic) run time. We empirically verify the speed up of our novel approximation and show that the faster approximation is able to keep up with the existing framework with respect to distance accuracy.
    04B - Beitrag Konferenzschrift