Exact GED: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Exact GED (Graph Edit Distance Computation)}} == 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. Exact GED computes the GED exactly. == Related Problems == Related: Inexact GED == Parameters == <pre>V: number of vertices in the larger of the two grap...") |
No edit summary |
||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
V: number of vertices in the larger of the two graphs | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Revision as of 12:02, 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. Exact GED computes the GED exactly.
Related Problems
Related: Inexact GED
Parameters
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} loglogE)$ | Exact | Deterministic | Time | |
| Tao D; Tang X; Li X et al | 2006 | $O(V^{2})$ | Exact | Deterministic | Time |
Time Complexity graph
Space Complexity graph
Pareto Decades graph
