Faster Subtree Isomorphism (extended abstract) Ron Shamir and Dekel Tzur. January 1997 To appear in Proc. ISTCS 97. Abstract We study the subtree isomorphism problem: Given trees $H$ and $G$, find a subtree of $G$ which is isomorphic to $H$ or decide that there is no such subtree. We give an $O(\frac{k^{1.5}}{\log k} n)$-time algorithm for this problem, where $k$ and $n$ are the number of vertices in $H$ and $G$ respectively. This improves over the $O(k^{1.5} n)$ 8 algorithms of Chung and Matula. We also give a randomized (Las Vegas) $O( \min(k^{1.45} n, k n^{1.43}))$-time algorithm for the decision problem.