On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree.
Massimo EquiRoberto GrossiVeli MäkinenPublished in: CoRR (2019)
Keyphrases
- pattern matching
- binary strings
- hamming distance
- bounded degree
- graph matching
- bounded treewidth
- graph theoretic
- string matching
- pattern matching algorithm
- regular expressions
- genetic algorithm
- encoding scheme
- bit parallel
- computational complexity
- decision problems
- boyer moore
- approximate pattern matching
- exact and approximate
- np complete
- relational databases
- objective function