Approximating Tree Edit Distance Through String Edit Distance

摘要

This paper presents an O(n~2) time algorithm for approximating the unit cost edit distance for ordered and rooted trees of bounded degree within a factor of O(n~(3/4)), where n is the maximum size of two input trees, and the algorithm is based on transformation of an ordered and rooted tree into a string.