Information Processing Letters 98 (2006) 253–262 A new tree inclusion algorithm

www.elsevier.com/locate/ipl We consider the following tree-matching problem: Given labeled, ordered trees P and T, can P be obtained from T by deleting nodes? Deleting a node v entails removing all edges incident to v and, if v has a parent u, replacing the edges from u to v by edges from u to the children of v. The existing algorithm for this problem needs O(|T | | leaves(P)|) time and O( | leaves(P) | min{DT,|leaves(T)|}) space, where leaves(P) (leaves(T)) stands for the number of the leaves of P(T),andDT for the height of T. In this paper, we present a new algorithm that requires O(|T | min{DP,|leaves(P)|}) time and no extra space, where DP represents the height of P. © 2006 Elsevier B.V. All rights reserved. 1