Exact GED (Graph Edit Distance Computation)
Revision as of 10:22, 15 February 2023 by Admin (talk | contribs) (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...")
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
Error creating thumbnail: Unable to save thumbnail to destination
Space Complexity graph
Error creating thumbnail: Unable to save thumbnail to destination
Pareto Decades graph
Error creating thumbnail: Unable to save thumbnail to destination