Recently, R. Kosaraju (Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, p.178-83) gave an O(nm/sup 0.75/ polylog(m))-step algorithm for tree pattern matching. The authors improve this result by designing a simple O(n square root m polylog (m)) algorithm. >
['Moshe Dubiner', 'Zvi Galil', 'Edith Magen']
Faster tree pattern matching