On the complexity of approximately matching a string to a directed graph.
Riccardo DondiGiancarlo MauriItalo ZoppisPublished in: Inf. Comput. (2022)
Keyphrases
- directed graph
- pattern matching
- random walk
- string matching
- approximate string matching
- matching algorithm
- computational complexity
- maximum flow
- shortest path problem
- undirected graph
- directed acyclic graph
- strongly connected
- approximate matching
- graph structure
- edit distance
- graph properties
- worst case
- disjoint paths
- data structure
- approximate pattern matching
- regular expressions
- keypoints
- markov chain
- dynamic programming