Tree pattern matching to subset matching in linear time

Richard Cole, Ramesh Hariharan

Research output: Contribution to journalArticlepeer-review


In this paper, we show an O(n + m) time Turing reduction from the tree pattern matching problem to another problem called the subset matching problem. Subsequent works have given efficient deterministic and randomized algorithms for the subset matching problem. Together, these works yield an O (n log 2 m + m) time deterministic algorithm and an O(n log n + m) time Monte Carlo algorithm for the tree pattern matching problem.

Original languageEnglish (US)
Pages (from-to)1056-1066
Number of pages11
JournalSIAM Journal on Computing
Issue number4
StatePublished - Jun 2003


  • Subset matching
  • Tree pattern matching

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Tree pattern matching to subset matching in linear time'. Together they form a unique fingerprint.

Cite this