Approximation algorithms for maximum two-dimensional pattern matching

DOI10.1016/S0304-3975(99)00153-XzbMATH Open0974.68041OpenAlexW2092188718WikidataQ127682245 ScholiaQ127682245MaRDI QIDQ5941062FDOQ5941062

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

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

zbMATH Keywords

approximation algorithmpattern matchingNP-lartness

Mathematics Subject Classification ID

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

Cites Work

• Applications of a Planar Separator Theorem
• Fast approximation algorithms for a nonconvex covering problem
• Title not available (Why is that?)
• Approximation algorithms for NP-complete problems on planar graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Parallel concepts in graph theory
• Title not available (Why is that?)
• Approximation schemes for covering and packing problems in image processing and VLSI
• Algorithmic Aspects of Vertex Elimination on Graphs
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Parameterized pattern matching: Algorithms and applications
• A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
• Optimal packing and covering in the plane are NP-complete
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (8)

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

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)