New and Improved Algorithms for Unordered Tree Inclusion The tree inclusion problem is, given two nodelabeled trees P and T (the pattern tree and the text tree), to locate every minimal subtree in T (if any) that can be obtained by applying a sequence of node insertion operations to P. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NPhard. The currently fastest algorithm for the latter is from 1995 and runs in O(poly(m,n) * 22d)  O*(22d) time, where m and n are the sizes of the pattern and text trees, respectively, and d is the maximum outdegree of the pattern tree. Here, we develop a new algorithm that improves the exponent 2d to d by considering a particular type of ancestordescendant relationships and applying dynamic programming, thus reducing the time complexity to O*(2d). We then study restricted variants of the unordered tree inclusion problem where the number of occurrences of different node labels andor the input treesu0027 heights are bounded. We show that although the problem remains NPhard in many such cases, it can be solved in polynomial time for c  2 and in O*(1.8d) time for c  3 if the leaves of P are distinctly labeled and each label occurs at most c times in T. We also present a randomized O*(1.883d)time algorithm for the case that the heights of P and T are one and two, respectively.

Cartesian Tree Matching and Indexing We introduce a new metric of match, called Cartesian tree matching, which means that two strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we define single pattern matching for a text of length n and a pattern of length m, and multiple pattern matching for a text of length n and k patterns of total length m. We present an O(nm) time algorithm for single pattern matching, and an O((nm) log k) deterministic time or O(nm) randomized time algorithm for multiple pattern matching. We also define an index data structure called Cartesian suffix tree, and present an O(n) randomized time algorithm to build the Cartesian suffix tree. Our efficient algorithms for Cartesian tree matching use a representation of the Cartesian tree, called the parentdistance representation.