Abstract
The main goal of this paper is to give an O(n log3 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 log3 n/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.
| Original language | English (US) |
|---|---|
| Pages | 245-254 |
| Number of pages | 10 |
| State | Published - 1999 |
| Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999 |
Other
| Other | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| City | Baltimore, MD, USA |
| Period | 1/17/99 → 1/19/99 |
ASJC Scopus subject areas
- Software
- General Mathematics