
We introduce the following optimization version of the classical pattern matching problem (referred to as the maximum pattern matching problem). Given a two-dimensional rectangular text and a two-dimensional rectangular pattern, find the maximum number of non-overlapping occurrences of the pattern in the text. Unlike the classical two-dimensional pattern matching problem, the maximum two-dimensional pattern matching problem is NP-complete. We devise polynomial time approximation algorithms and approximation schemes for this problem. We also briefly discuss how the approximation algorithms can be extended to include a number of other variants of the problem.
Design, Image Processing, Pattern Recognition, Two-Dimensional Calculations, 510, Theoretical Computer Science, Symmetry, Digital Systems, Pattern matching, Information Science, approximation algorithm, Computers, NP-lartness, 99 Mathematics, Approximation algorithm, Management, Miscellaneous, 004, pattern matching, Parallel algorithms in computer science, Law, Searching and sorting, Algorithms, Computer Science(all)
Design, Image Processing, Pattern Recognition, Two-Dimensional Calculations, 510, Theoretical Computer Science, Symmetry, Digital Systems, Pattern matching, Information Science, approximation algorithm, Computers, NP-lartness, 99 Mathematics, Approximation algorithm, Management, Miscellaneous, 004, pattern matching, Parallel algorithms in computer science, Law, Searching and sorting, Algorithms, Computer Science(all)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
