An Isolated-Subtree Inclusion for Unordered Trees
Takahiro Hokazono, Tomohiro Kan, Yoshiyuki Yamamoto, Kouichi Hirata · 2012
An unordered tree inclusion is the problem of determining whether or not an unordered tree P is included in an unordered tree T. In this paper, we introduce an isolated-sub tree inclusion by restricting that disjoint sub trees of P are always included in disjoint sub trees of T. Then, we design the algorithm to solve the isolated-sub tree inclusion in O(|T|·|P|1.5) time and in O(|T|·|P|) space.