Inexact GED

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.

Parameters

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 5 of 5 algorithms


Y Bai	2018	$O(V^2)$	$O(V^2)$
L Chang	2017	$O(V E^2 \log V)$	$O(V)$
K Riesen	2013	$O(V^2)$	$O(V)$
Neuhaus, Riesen, Bunke	2006	$O(V^2)$	$O(wV)$
Finch	1998	$O(V^2 E)$	$O(V^2)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms