Cole, Richard ; Hariharan, Ramesh (2003) Tree pattern matching to subset matching in linear time SIAM Journal on Computing, 32 (4). pp. 1056-1066. ISSN 0097-5397
Full text not available from this repository.
Official URL: http://epubs.siam.org/doi/abs/10.1137/S00975397003...
Related URL: http://dx.doi.org/10.1137/S0097539700382704
Abstract
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 (nlog2m +m) time deterministic algorithm and an O (n log n+m) time Monte Carlo algorithm for the tree pattern matching problem.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Society for Industrial and Applied Mathematics. |
| ID Code: | 102277 |
| Deposited On: | 09 Mar 2018 11:27 |
| Last Modified: | 09 Mar 2018 11:27 |
Repository Staff Only: item control page
