The Complexity of Two-Dimensional Compressed Pattern Matching
Title | The Complexity of Two-Dimensional Compressed Pattern Matching |
Publication Type | Technical Report |
Year of Publication | 1996 |
Authors | Berman, P., Karpinski M., Larmore L. L., Plandowski W., & Rytter W. |
Other Numbers | 1060 |
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. |
URL | http://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 |