% 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}
@inproceedings{faucris.259226018,
abstract = {The graph edit distance is a well-established and widely used distance measure for labelled, undirected graphs. However, since its exact computation is NP-hard, research has mainly focused on devising approximative heuristics and only few exact algorithms have been proposed. The standard approach A{\_}-GED, a node-based best-first search that works for both uniform and non-uniform metric edit costs, suffers from huge runtime and memory requirements. Recently, two better performing algorithms have been proposed: DF-GED, a node-based depth-first search that works for uniform and non-uniform metric edit costs, and CSI GED, an edge-based depth-first search that works only for uniform edit costs. Our paper contains two contributions: First, we propose a speed-up DF-GEDu of DF-GED for uniform edit costs. Second, we develop a generalisation CSI GEDnu of CSI GED that also covers non-uniform metric edit cost. We empirically evaluate the proposed algorithms. The experiments show, i.a., that our speed-up DF-GEDu clearly outperforms DF-GED and that our generalisation CSI GEDnu is the most versatile algorithm.},
author = {Blumenthal, David B. and Gamper, Johann},
booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
date = {2017-05-16/2017-05-18},
doi = {10.1007/978-3-319-58961-9{\_}19},
editor = {Pasquale Foggia, Mario Vento, Cheng-Lin Liu},
faupublication = {yes},
isbn = {9783319589602},
keywords = {Branch and bound; Graph edit distance; Graph matching; Graph similarity},
note = {CRIS-Team Scopus Importer:2021-05-26},
pages = {211-221},
peerreviewed = {unknown},
publisher = {Springer Verlag},
title = {{Exact} computation of graph edit distance for uniform and non-uniform metric edit costs},
venue = {Anacapri, ITA},
volume = {10310 LNCS},
year = {2017}
}