SUBTREE ISOMORPHISM IS IN DLOG FOR NESTED TREES
Raymond Greenlaw · International Journal of Foundations of Computer Science · 1996
This research shows subtree isomorphism is in DLOG, and hence [Formula: see text], for nested trees. To our knowledge this result provides the first interesting class of trees for which the problem is in a non-randomized version of [Formula: see text]. We also show that one can determine whether or not an arbitrary tree is a nested tree in DLOG.