Approximation algorithms for maximum two-dimensional pattern matching

DOI10.1016/S0304-3975(99)00153-XzbMath0974.68041OpenAlexW2092188718WikidataQ127682245 ScholiaQ127682245MaRDI QIDQ5941062

Andrzej Lingas, Anders Dessmark, Madhav V. Marathe, Srinivasa R. Arikati

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

zbMATH Keywords

approximation algorithmpattern matchingNP-lartness

Mathematics Subject Classification ID

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

Related Items

Maximum packing for biconnected outerplanar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Graph minors. II. Algorithmic aspects of tree-width
• Approximation schemes for covering and packing problems in image processing and VLSI
• Fast approximation algorithms for a nonconvex covering problem
• Applications of a Planar Separator Theorem
• Algorithmic Aspects of Vertex Elimination on Graphs
• A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• Approximation algorithms for NP-complete problems on planar graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph