Skip to Main content Skip to Navigation
Journal articles

On the Tree Inclusion Problem

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
Complete list of metadata
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

Links full text




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