On the tree inclusion problem |
| |
Authors: | Laurent Alonso René Schott |
| |
Affiliation: | (1) INRIA-Lorraine and LORIA, Université Henri Poincaré-Nancy 1, 54506 Vandoeuvre-lès-Nancy, France , FR;(2) IECN and LORIA, Université Henri Poincaré-Nancy 1, 54506 Vandoeuvre-lès-Nancy, France , FR |
| |
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 means replacing the subtree by the trees . 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 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 barrier.
Received: 4 November 1996 / 2 March 2001 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|