Inexact GED

Description

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. Inexact GED computes an answer that is not gauranteed to be the exact GED.

Related Problems

Related: Exact GED

Parameters

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

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Y Bai	2018	$O(V^{2})$	$O(V^{2})$	none stated	Deterministic	Time
L Chang	2017	$O(V E^{2} logV)$	$O(V)$	Exact	Deterministic	Time & Space
K Riesen	2013	$O(V^{2})$	$O(V)$	Exact	Deterministic	Time
Alberto Sanfeliu and King-Sun Fu	1983	$O(V^{3} E^{2})$		Exact	Deterministic	Time
Neuhaus, Riesen, Bunke	2006	$O(V^{2})$	$O(wV)$	Exact	Deterministic	Time
Wang Y-K; Fan K-C; Horng J-T	1997	$O(V E^{2} loglogE)$		Exact	Deterministic	Time
Tao D; Tang X; Li X et al	2006	$O(V^{2})$		Exact	Deterministic	Time
Finch	1998	$O(V^{2} E)$	$O(V^{2})$?	Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff