Abstract
Very recently, Chen and Chen [Y. Chen, Y. Chen, A new tree inclusion algorithm, Information Processing Letters 98 (2006) 253-262] gave a new algorithm for the tree inclusion problem, which requires O (| T | × min {depth (P), | leaves (P) |}) time and no extra space. In this Note, we show that there are flaws in their time-complexity analysis by presenting two counterexamples. We also give an example to show that the worst-case time complexity of their algorithm is non-polynomial. Consequently, the asymptotically most efficient algorithm for the tree inclusion problem is the former algorithm in [W. Chen, More efficient algorithm for ordered tree inclusion, Journal of Algorithms 26 (1998) 370-385]. © 2007 Elsevier B.V. All rights reserved.