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 mathtt {A}^star -mathtt {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: mathtt {DF}-mathtt {GED}, a node-based depth-first search that works for uniform and non-uniform metric edit costs, and mathtt {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 mathtt {DF}-mathtt {GED^{u}} of mathtt {DF}-mathtt {GED} for uniform edit costs. Second, we develop a generalisation mathtt {CSI_GED^{nu}} of mathtt {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 mathtt {DF}-mathtt {GED^{u}} clearly outperforms mathtt {DF}-mathtt {GED} and that our generalisation mathtt {CSI_GED^{nu}} is the most versatile algorithm.