Exact GED (Graph Edit Distance Computation)

From Algorithm Wiki
Jump to navigation Jump to search


The GED of two graphs is defined as the minimum cost of an edit path between them, where an edit path is a sequence of edit operations (inserting, deleting, and relabeling vertices or edges) that transforms one graph into another. Exact GED computes the GED exactly.

Related Problems

Related: Inexact GED


$V$: number of vertices in the larger of the two graphs

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
X Chen 2019 $O(VS)$ $O(wV^{2})$ Exact Deterministic Time & Space
Alberto Sanfeliu and King-Sun Fu 1983 $O(V^{3} E^{2})$ Exact Deterministic Time
Wang Y-K; Fan K-C; Horng J-T 1997 $O(V E^{2} \log \log E)$ Exact Deterministic Time
Tao D; Tang X; Li X et al 2006 $O(V^{2})$ Exact Deterministic Time

Time Complexity Graph

Graph Edit Distance Computation - Exact GED - Time.png