HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Wednesday, September 21, 2005 - 4:40:12 PM
Last modification on : Friday, February 4, 2022 - 3:25:17 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