1998 ComputingTheEditDistBetUnrootOrdTrees
Jump to navigation
Jump to search
- (Klein, 1998) ⇒ Philip N. Klein. (1998). “Computing the Edit-Distance Between Unrooted Ordered Trees.” Algorithms — ESA’ 98. doi:10.1007/3-540-68530-8
Subject Headings: Tree Edit Distance Function.
Notes
Quotes
Abstract
- An ordered tree is a tree in which each node’s incident edges are cyclically ordered; think of the tree as being embedded in the plane. Let A and B be two ordered trees. The edit distance between A and B is the minimum cost of a sequence of operations (contract an edge, uncontract an edge, modify the label of an edge) needed to transform A into B. We give an O(n3 log n) algorithm to compute the edit distance between two ordered trees.
,
| Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1998 ComputingTheEditDistBetUnrootOrdTrees | Philip N. Klein | Computing the Edit-Distance Between Unrooted Ordered Trees | 10.1007/3-540-68530-8 |