Parallel two dimensional witness computation

Richard Cole, Zvi Galil, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park

Research output: Contribution to journalArticlepeer-review


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 log m) time and does O(m1 × m 2) work, where m = max{m1, m2}. This yields a work optimal algorithm for 2D pattern matching which takes O (log log m) preprocessing time and O(1) text processing time.

Original languageEnglish (US)
Pages (from-to)20-67
Number of pages48
JournalInformation and Computation
Issue number1
StatePublished - Jan 10 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Parallel two dimensional witness computation'. Together they form a unique fingerprint.

Cite this