Exact algorithms for computing the tree edit distance between unordered trees

摘要

This paper presents a fixed-parameter algorithm for the tree edit distance problem for unordered trees under the unit cost model that works in 0(2.62~k · poly(n)) time and O(n~2) space, where the parameter k is the maximum bound of the edit distance and n is the maximum size of input trees. This paper also presents polynomial-time algorithms for the case where the maximum degree of the largest common subtree is bounded by a constant.