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

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