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

Fast linear sum assignment with error-correction and no cost constraints

Sébastien Bougleux 1 Benoit Gaüzère 2, 3 David Blumenthal 4 Luc Brun 1
1 Equipe Image - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
3 DocApp - LITIS - Equipe Apprentissage
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Abstract : We propose an algorithm that efficiently solves the linear sum assignment problem with error-correction and no cost constraints. This problem is encountered for instance in the approximation of the graph edit distance. The fastest currently available solvers for the linear sum assignment problem require the pairwise costs to respect the triangle inequality. Our algorithm is as fast as these algorithms, but manages to drop the cost constraint. The main technical ingredient of our algorithm is a cost-dependent factorization of the node substitutions.
Liste complète des métadonnées

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

https://hal-normandie-univ.archives-ouvertes.fr/hal-02110718
Contributeur : Benoit Gaüzère <>
Soumis le : jeudi 11 juillet 2019 - 10:25:30
Dernière modification le : jeudi 5 mars 2020 - 10:48:02

Fichier

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

Identifiants

Citation

Sébastien Bougleux, Benoit Gaüzère, David Blumenthal, Luc Brun. Fast linear sum assignment with error-correction and no cost constraints. Pattern Recognition Letters, Elsevier, 2018, ⟨10.1016/j.patrec.2018.03.032⟩. ⟨hal-02110718⟩

Partager

Métriques

Consultations de la notice

83

Téléchargements de fichiers

113