D.W. MATULA, Washington University, St. Louis, Missouri. An Algorithm for Subtree Identification.

Given the tree T with N nodes, where the maximal degree of any node is D, and another tree t with n < N nodes, where the maximal degree of any node is d £ D, we give an efficient algorithm for determining if t is a subtree of T. The algorithm involves the solution of less than 2Nn network flow problems, each of a particularly simple bipartite structure involving at most dD arcs of unit capacity, where the maximal flow can be no greater than d. Since the maximal degree of the nodes of a tree will, on the average, only grow with the log of the number of nodes, the total effort necessary to determine if t is a subtree of T should grow only slightly faster than the product Nn; thus the algorithm avoids the exponential growth characteristic incumbent in many "solutions" of combinatorial problems. The algorithm is also applicable to chromatic trees, thus providing a solution to the chemical substructure search problem for molecules which are either ring free or which contain only simple (nonfused) rings.