Parallel two dimensional witness computation

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:

Related URL:


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