Klein, Philip N. Computing the edit-distance between unrooted ordered trees. (English) Zbl 0932.68066 Bilardi, Gianfranco (ed.) et al., Algorithms - ESA ’98. 6th annual European symposium, Venice, Italy, August 24–26, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1461, 91-102 (1998). Summary: 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(n^3\log n)\) algorithm to compute the edit distance between two ordered trees.For the entire collection see [Zbl 0895.00050]. Cited in 5 ReviewsCited in 31 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 05C85 Graph algorithms (graph-theoretic aspects) 05C05 Trees Keywords:ordered tree PDFBibTeX XMLCite \textit{P. N. Klein}, Lect. Notes Comput. Sci. 1461, 91--102 (1998; Zbl 0932.68066)