Exact GED: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
V: number of vertices in the larger of the two graphs | $V$: number of vertices in the larger of the two graphs | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 24: | Line 24: | ||
| [[Alberto Sanfeliu and King-Sun Fu ( Graph Edit Distance Computation)|Alberto Sanfeliu and King-Sun Fu]] || 1983 || $O(V^{3} E^{2})$ || || Exact || Deterministic || [https://doi.org/10.1109/TSMC.1983.6313167 Time] | | [[Alberto Sanfeliu and King-Sun Fu ( Graph Edit Distance Computation)|Alberto Sanfeliu and King-Sun Fu]] || 1983 || $O(V^{3} E^{2})$ || || Exact || Deterministic || [https://doi.org/10.1109/TSMC.1983.6313167 Time] | ||
|- | |- | ||
| [[Wang Y-K; Fan K-C; Horng J-T ( Graph Edit Distance Computation)|Wang Y-K; Fan K-C; Horng J-T]] || 1997 || $O(V E^{2} | | [[Wang Y-K; Fan K-C; Horng J-T ( Graph Edit Distance Computation)|Wang Y-K; Fan K-C; Horng J-T]] || 1997 || $O(V E^{2} \log \log E)$ || || Exact || Deterministic || [https://doi.org/10.1109/3477.604100 Time] | ||
|- | |- | ||
| [[Tao D; Tang X; Li X et al ( Graph Edit Distance Computation)|Tao D; Tang X; Li X et al]] || 2006 || $O(V^{2})$ || || Exact || Deterministic || [https://eprints.bbk.ac.uk/id/eprint/443/1/Binder1.pdf Time] | | [[Tao D; Tang X; Li X et al ( Graph Edit Distance Computation)|Tao D; Tang X; Li X et al]] || 2006 || $O(V^{2})$ || || Exact || Deterministic || [https://eprints.bbk.ac.uk/id/eprint/443/1/Binder1.pdf Time] | ||
| Line 30: | Line 30: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Graph Edit Distance Computation - Exact GED - Time.png|1000px]] | [[File:Graph Edit Distance Computation - Exact GED - Time.png|1000px]] | ||
Latest revision as of 09:09, 28 April 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} \log \log E)$ | Exact | Deterministic | Time | |
| Tao D; Tang X; Li X et al | 2006 | $O(V^{2})$ | Exact | Deterministic | Time |
Time Complexity Graph
