# On the Tree Inclusion Problem

1 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Document type :
Journal articles

https://hal.inria.fr/inria-00000272
Contributor : Agnès Vidard <>
Submitted on : Wednesday, September 21, 2005 - 4:40:12 PM
Last modification on : Tuesday, April 6, 2021 - 11:48:24 AM

### Citation

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

Record views