Faster Tree Pattern Matching

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. >

Authors

• Moshe Dubiner
• Zvi Galil
• Edith Magen

Keywords

• Pattern matching
• Partitioning algorithms
• Algorithm design and analysis
• Mathematics
• Convolution
• Path Length
• Length Of Period
• Search String
• Linear Time
• Node Labels
• Place In Period
• Naive Algorithm
• Cyclic Permutation