Inexact GED: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| 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 30: | Line 30: | ||
| [[Neuhaus, Riesen, Bunke (Inexact GED Graph Edit Distance Computation)|Neuhaus, Riesen, Bunke]] || 2006 || $O(V^{2})$ || $O(wV)$ || Exact || Deterministic || [https://link.springer.com/chapter/10.1007/11815921_17 Time] | | [[Neuhaus, Riesen, Bunke (Inexact GED Graph Edit Distance Computation)|Neuhaus, Riesen, Bunke]] || 2006 || $O(V^{2})$ || $O(wV)$ || Exact || Deterministic || [https://link.springer.com/chapter/10.1007/11815921_17 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] | ||
Revision as of 08:22, 10 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. 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} \log \log E)$ | 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
Space Complexity Graph
Time-Space Tradeoff
