Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Comparing heuristics for graph edit distance computation

David Blumenthal 1 Nicolas Boria 2 Johann Gamper 1 Sébastien Bougleux 2 Luc Brun 2
2 Equipe Image - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : Because of its flexibility, intuitiveness, and ex-pressivity, the graph edit distance (GED) is one of the most widely used distance measures for labeled graphs. Since exactly computing GED is NP-hard, over the past years, various heuristics have been proposed. They use techniques such as transformations to the linear sum assignment problem with error-correction, local search, and linear programming to approximate GED via upper or lower bounds. In this paper , we provide a systematic overview of the most important heuristics. Moreover, we empirically evaluate all compared heuristics within an integrated implementation.
Liste complète des métadonnées

Littérature citée [75 références]  Voir  Masquer  Télécharger

https://hal-normandie-univ.archives-ouvertes.fr/hal-02189832
Contributeur : Luc Brun <>
Soumis le : samedi 20 juillet 2019 - 12:08:56
Dernière modification le : jeudi 13 février 2020 - 13:57:05

Fichier

AAM_VLDB_J_2019.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

David Blumenthal, Nicolas Boria, Johann Gamper, Sébastien Bougleux, Luc Brun. Comparing heuristics for graph edit distance computation. The VLDB Journal, Springer, 2020, 29 (1), pp.419-458. ⟨10.1007/s00778-019-00544-1⟩. ⟨hal-02189832⟩

Partager

Métriques

Consultations de la notice

69

Téléchargements de fichiers

46