Approximation Algorithms for Maximum Two-Dimensional Pattern Matching.
Srinivasa Rao ArikatiAnders DessmarkAndrzej LingasMadhav V. MarathePublished in: CPM (1996)
Keyphrases
- pattern matching
- approximation algorithms
- np hard
- vertex cover
- worst case
- special case
- primal dual
- minimum cost
- tree matching
- regular expressions
- pattern matching algorithm
- integrality gap
- multi dimensional
- string matching
- approximation ratio
- set cover
- open shop
- matching process
- boyer moore
- disjoint paths
- constant factor
- randomized algorithms
- bit parallel
- precedence constraints
- compressed pattern matching
- approximation schemes
- polynomial time approximation
- search engine
- matching algorithm
- linear programming
- computational complexity
- data structure