Identifying approximately common substructures in trees based on a restricted edit distance

In this paper we present a dynamic programming algorithm for identifying the largest approximately common substructures (LACSs) of two ordered labeled trees. We consider a substructure of a tree T to be a connected subgraph of T. Given two trees T₁, T₂ and an integer d, the LACS problem is to find a substructure U₁ of T₁ and a substructure U₂ of T₂ such that U₁ is within distance d of U₂ and where there does not exist any other substructure V₁ of T₁ and V₂ of T₂ such that V₁ and V₂ satisfy the distance restriction and the sum of the sizes of V₁ and V₂ is greater than the sum of the sizes of U₁ and U₂. The distance measure considered in the paper is a restricted edit distance originated from Selkow. The LACS problem is motivated by the studies of program and document comparison. The proposed algorithm solves the problem in time O(d²×|T₁|×|T₂|), which is as fast as the best known algorithm for calculating Selkow's distance of two trees when the distance allowed in the common substructures is a constant independent of the input trees.