View article

This paper considers the problem of computing a constrained edit distance between unordered labeled trees. The problem of approximate unordered tree matching is also considered. We present dynamic programming algorithms solving these problems in sequential timeO(|T ₁|×|T ₂|×(deg(T ₁)+deg(T ₂))× log₂(deg(T ₁)+deg(T ₂))). Our previous result shows that computing the edit distance between unordered labeled trees is NP-complete.