Approximation algorithms for maximum two-dimensional pattern matching

DOI10.1016/S0304-3975(99)00153-XMaRDI QIDQ5941062zbMATH OpenOpenAlexWikidataFDO

Authors S. R. Arikati, Anders Dessmark, Andrzej Lingas, Madhav V. Marathe

Publication date 20 August 2001

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(99)00153-x, https://www.osti.gov/biblio/248298

zbMATH Keywords

approximation algorithmNP-lartnesspattern matching

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Review text

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.

Recommendations

• Efficient 2-dimensional approximate matching of half-rectangular figures
• Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time
• scientific article; zbMATH DE number 1003305
• Two-dimensional dictionary matching
• Fast two-dimensional pattern matching

Cites work

• A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Fast approximation algorithms for a nonconvex covering problem
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 432822 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 1263250 (Why is no real title available?)
• scientific article; zbMATH DE number 1306895 (Why is no real title available?)
• scientific article; zbMATH DE number 194543 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• Optimal packing and covering in the plane are NP-complete
• Parallel concepts in graph theory
• Parameterized pattern matching: Algorithms and applications
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(8)

• Dynamic and approximate pattern matching in 2D
• On the computational complexity of 2-interval pattern matching problems
• Maximum packing for biconnected outerplanar graphs
• Approximation algorithms for Max Morse matching
• Two-dimensional pattern matching in linear time and small space
• Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time
• On linear-time alphabet-independent 2-dimensional pattern matching
• Algorithms – ESA 2005

This page was built for publication: Approximation algorithms for maximum two-dimensional pattern matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941062)