EXACT AND APPROXIMATE ALGORITHMS FOR UNORDERED TREE MATCHING

We consider the problem of comparison between unordered trees, i.e., t rees for which the order among siblings is unimportant. The criterion for comparison is the distance as measured by a weighted sum of the co sts of deletion, insertion and relabel operations on tree nodes. Such comparisons may contribute to pattern recognition efforts in any field (e.g., genetics) where data can naturally be characterized by unorder ed trees. In companion work, we have shown this problem to be NP-compl ete. This paper presents an efficient enumerative algorithm and severa l heuristics leading to approximate solutions. The algorithms are base d on probabilistic hill climbing and bipartite matching techniques. Th e paper evaluates the accuracy and time efficiency of the heuristics b y applying them to a set of trees transformed from industrial parts ba sed on a previously proposed morphological model.