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

Bougleux S, Gauzere B, Blumenthal DB, Brun L (2020)

Publication Type: Journal article

Publication year: 2020

Journal

Pattern Recognition Letters Elsevier

Book Volume: 134

Pages Range: 37-45

DOI: 10.1016/j.patrec.2018.03.032

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.

Authors with CRIS profile

David Blumenthal Professur für Biomedical Network Science

Involved external institutions

Université de Caen Basse-Normandie FR France (FR)

How to cite

APA:

Bougleux, S., Gauzere, B., Blumenthal, D.B., & Brun, L. (2020). Fast linear sum assignment with error-correction and no cost constraints. Pattern Recognition Letters, 134, 37-45. https://dx.doi.org/10.1016/j.patrec.2018.03.032

MLA:

Bougleux, Sebastien, et al. "Fast linear sum assignment with error-correction and no cost constraints." Pattern Recognition Letters 134 (2020): 37-45.

BibTeX: Download