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 |