A VLSI Algorithm for Calculating the Tree to Tree Distance

Given two ordered,labeled trees β and α,to find the distance from tree β to tree α is an important problem in many fields,for example,the pattern recognition field.In this paper,a VLSI algorithm for calculating the tree-to-tree distance is presented.The computation structure of the algorithm is a 2-D Mesh with the size m*n-and the time is O(m+n),where m,n are the numbers of nodes of the tree β and tree α,respectively.