Tree pattern matching and subset matching in deterministic O(n log3 n)-time

Richard Cole, Ramesh Hariharan, Piotr Indyk

Research output: Contribution to conferencePaper

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 languageEnglish (US)
Pages245-254
Number of pages10
StatePublished - 1999
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/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<sup>3</sup> n)-time'. Together they form a unique fingerprint.

Cite this