
Future Communication, Information and Computer Science – Zheng (Ed.)
© 2015 Taylor & Francis Group, London, 978-1-138-02653-7
A time and space efficient algorithm for the tree inclusion problem
Y.J. Chen & Y.B. Chen
University of Winnipeg, Winnipeg, Manitoba, Canada
ABSTRACT: The ordered tree inclusion is an interesting problem, by which we will check whether a pattern
tree P can be included in a target tree T, in which the order of siblings is significant. In this paper, we propose an
efficient algorithm for this problem. Its time complexity is bounded by O(|T |·d
P
· log h
P
), where d
P
represents
the largest out-degree of a node in P and h
P
is the height ...