Approximating GED using a Stochastic Generator and Multistart IPFP - Normandie Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Approximating GED using a Stochastic Generator and Multistart IPFP

Résumé

The Graph Edit Distance defines the minimal cost of a sequence of elementary operations transforming a graph into another graph. This versatile concept with an intuitive interpretation is a fundamental tool in structural pattern recognition. However, the exact computation of the Graph Edit Distance is N P-complete. Iterative algorithms such as the ones based on Franck-Wolfe method provide a good approximation of true edit distance with low execution times. However, underlying cost function to optimize being neither concave nor convex, the accuracy of such algorithms highly depends on the initialization. In this paper, we propose a smart random initializer using promising parts of previously computed solutions.
Fichier principal
Vignette du fichier
sspr18approx-ged-stoch-gen(1).pdf (370.6 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01865351 , version 1 (31-08-2018)

Identifiants

  • HAL Id : hal-01865351 , version 1

Citer

Nicolas Boria, Sébastien Bougleux, Luc Brun. Approximating GED using a Stochastic Generator and Multistart IPFP. S+SSPR 2018, Aug 2018, Beijing, China. ⟨hal-01865351⟩
124 Consultations
206 Téléchargements

Partager

Gmail Facebook X LinkedIn More