# zbMATH — the first resource for mathematics

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].

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 05C85 Graph algorithms (graph-theoretic aspects) 05C05 Trees
ordered tree