Cole, Richard ; Galil, Zvi ; Hariharan, Ramesh ; Muthukrishnan, S. ; Park, Kunsoo (2004) Parallel two dimensional witness computation Information and Computation, 188 (1). pp. 20-67. ISSN 0890-5401
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/pii/S...
Related URL: http://dx.doi.org/10.1016/S0890-5401(03)00162-7
Abstract
An optimal parallel CRCW-PRAM algorithm to compute witnesses for all non-period vectors of an m1×m2 pattern is given. The algorithm takes O(log logm) time and does O(m1×m2) work, where m = max{m1,m2}. This yields a work optimal algorithm for 2D pattern matching which takes O(log logm) preprocessing time and O(1) text processing time.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 102283 |
| Deposited On: | 09 Mar 2018 11:23 |
| Last Modified: | 09 Mar 2018 11:23 |
Repository Staff Only: item control page
