The Complexity of Two-Dimensional Compressed Pattern Matching

TitleThe Complexity of Two-Dimensional Compressed Pattern Matching
Publication TypeTechnical Report
Year of Publication1996
AuthorsBerman, P., Karpinski M., Larmore L. L., Plandowski W., & Rytter W.
Other Numbers1060
Abstract

We study computational complexity of two-dimensional compressed pattern matching problems. Among other things, we design an efficient randomized algorithm for the equality problem of two compressed two-dimensional patterns as well as prove computational {em hardness} of the general two-dimensional compressed pattern matching.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1996/tr-96-051.pdf
Bibliographic Notes

ICSI Technical Report TR-96-051

Abbreviated Authors

P. Berman, M. Karpinski, L. Larmore, W. Plandowski, and W. Rytter

ICSI Publication Type

Technical Report