Inexact GED: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 46: Line 46:
[[File:Graph Edit Distance Computation - Inexact GED - Space.png|1000px]]
[[File:Graph Edit Distance Computation - Inexact GED - Space.png|1000px]]


== Pareto Frontier Improvements Graph ==  
== Space-Time Tradeoff Improvements ==  


[[File:Graph Edit Distance Computation - Inexact GED - Pareto Frontier.png|1000px]]
[[File:Graph Edit Distance Computation - Inexact GED - Pareto Frontier.png|1000px]]

Revision as of 14:37, 15 February 2023

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

Graph Edit Distance Computation - Inexact GED - Time.png

Space Complexity Graph

Graph Edit Distance Computation - Inexact GED - Space.png

Space-Time Tradeoff Improvements

Graph Edit Distance Computation - Inexact GED - Pareto Frontier.png