Publication Details
Title: The Complexity of Two-Dimensional Compressed Pattern Matching
Author: P. Berman, M. Karpinski, L. Larmore, W. Plandowski, and W. Rytter
Group: ICSI Technical Reports
Date: December 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-051.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-96-051
Bibliographic Reference:
P. Berman, M. Karpinski, L. Larmore, W. Plandowski, and W. Rytter. The Complexity of Two-Dimensional Compressed Pattern Matching. ICSI Technical Report TR-96-051, December 1996
Author: P. Berman, M. Karpinski, L. Larmore, W. Plandowski, and W. Rytter
Group: ICSI Technical Reports
Date: December 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-051.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-96-051
Bibliographic Reference:
P. Berman, M. Karpinski, L. Larmore, W. Plandowski, and W. Rytter. The Complexity of Two-Dimensional Compressed Pattern Matching. ICSI Technical Report TR-96-051, December 1996