An Analysis of a Good Algorithm for the Subtree Problem

Abstract

A good algorithm is analyzed for deciding if one tree is a subtree of another tree. If both trees are rooted, the smaller tree has n vertices and the larger has m vertices; then the total number of computations is $O(nm^{1.5})$ or better, depending on how good an algorithm one has for a maximal matching in a bipartite graph.