Veli Mäkinen

On the Complexity of String Matching for Graphs

2023 · ACM Transactions on Algorithms

Exact string matching in labeled graphs is the problem of searching paths of a graph G=(V, E) such that the concatenation of their node labels is equal to a given pattern string P [1. m …