D. Shasha et al., EXACT AND APPROXIMATE ALGORITHMS FOR UNORDERED TREE MATCHING, IEEE transactions on systems, man, and cybernetics, 24(4), 1994, pp. 668-678
Citations number
39
Categorie Soggetti
Controlo Theory & Cybernetics","Computer Science Cybernetics","Engineering, Eletrical & Electronic
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.