Richard Cole, Ramesh Hariharan, Piotr Indyk

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, 245-245.

The main goal of this paper is to give an O(n log^3 n) time deterministic algorithm for the Subset Matching problem. This immediately yields an algorithm of the same efficiency for the Tree Pattern Matching problem. We also give an O(n log^3 / log log n) time randomized algorithm for these problems. Finally, we give a O(n log n (z + log n)) time deterministic algorithm for a useful specialization of the Subset Matching problem in which all sets are intervals of a given length z.

postscript of full paper