## Abstract

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} 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
- Mathematics(all)

## Fingerprint

Dive into the research topics of 'Tree pattern matching and subset matching in deterministic O(n log^{3}n)-time'. Together they form a unique fingerprint.