% Encoding: UTF-8
@COMMENT{BibTeX export based on data in FAU CRIS: https://cris.fau.de/}
@COMMENT{For any questions please write to cris-support@fau.de}
@article{faucris.259223248,
abstract = {The graph edit distance is a widely used distance measure for labelled graph. However, A^{★}−GED, the standard approach for its exact computation, suffers from huge runtime and memory requirements. Recently, three better performing algorithms have been proposed: The general algorithms DF−GED and BIP−GED, and the algorithm CSI−GED, which only works for uniform edit costs. All newly proposed algorithms outperform the standard approach A^{★}−GED. However, cross-comparisons are lacking. This paper consolidates and extends these recent advances. To this purpose, we present all existing algorithms in a unified way and show that the slightly different definitions of the graph edit distance underlying A^{★}−GED and DF−GED, on the one side, and CSI−GED, on the other side, can be harmonised. This harmonisation allows us to develop a generalisation of CSI−GED to non-uniform edit cost. Moreover, we present a speed-up of A^{★}−GED and DF−GED for uniform edit costs, which build upon the fact that, in the uniform case, a continuously used subroutine can be implemented to run in linear rather than cubic time. We also suggest an algorithm MIP−GED which builds upon a very compact new mixed integer linear programming formulation. Finally, we carry out a thorough empirical evaluation, which, for the first time, compares all existing exact algorithms.},
author = {Blumenthal, David B. and Gamper, Johann},
doi = {10.1016/j.patrec.2018.05.002},
faupublication = {no},
journal = {Pattern Recognition Letters},
keywords = {Best-first search; Depth-first search; Exact algorithms; Graph edit distance; Integer programming},
note = {CRIS-Team Scopus Importer:2021-05-26},
pages = {46-57},
peerreviewed = {Yes},
title = {{On} the exact computation of the graph edit distance},
volume = {134},
year = {2020}
}