On the Tree Inclusion Problem

Laurent Alonso (1) , René Schott (2, 3)

1 ISA - Models, algorithms and geometry for computer graphics and vision
2 IECN - Institut Élie Cartan de Nancy
3 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

We consider the following problem: Given ordered labeled trees S and T can S be obtained from T by deleting nodes? Deletion of the root node u of a subtree with children $(T_1, \ldots,T_n)$ means replacing the subtree by the trees $T_1, \ldots,T_n$. For the tree inclusion problem, there can generally be exponentially many ways to obtain the included tree. P. Kilpelinen and H. Mannila [5,7] gave an algorithm based on dynamic programming requiring $O(\mid S\mid.\mid T \mid)$ time and space in the worst case and also on the average for solving this problem. We give an algorithm whose idea is similar to that of [5,7] but which improves the previous one and on the average breaks the $\mid S\mid.\mid T \mid$ barrier.

Domaines: Algorithme et structure de données [cs.DS]

Laurent Alonso, René Schott. On the Tree Inclusion Problem. Acta Informatica, 2001, 37 (9), pp.653-670. ⟨10.1007/PL00013317⟩. ⟨inria-00000272⟩