Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond
We present the first parameterized algorithms for SMLG in DAGs, derived from a generalization of the Knuth-Morris-Pratt algorithm optimized to work in time proportional to the number of prefix-incomparable matches. We obtain parameterizations in the topological structure of $G$, by studying a special class of DAGs called funnels and generalizing them to $k$-funnels and the class $ST_k$.
Jun 26, 2023
