Preprint
Aug 2026
A Separator-based Algorithm for the Graph Edit Distance Problem
A novel exponential time algorithm is presented to compute the exact GED and a corresponding edit sequence in $O^*(4 + \varepsilon)^n$ time and polynomial space, provided one of the two graphs admits strictly sublinear balanced separators.
L. Bülte, Philip Mayer, Lars Müller et al.
· 0 citations