A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs

Marie-Louise Bruner, Martin Lackner

The NP-complete Permutation Pattern Matching problem asks whether a $k$-permutation $P$ is contained in a $n$-permutation $T$ as a pattern. This is the case if there exists an orde…