Michael H. Albert ; Marie-Louise Lackner ; Martin Lackner ; Vincent Vatter
-
The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged
Permutations
The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged
PermutationsArticle
Authors: Michael H. Albert ; Marie-Louise Lackner ; Martin Lackner ; Vincent Vatter
NULL##NULL##NULL##0000-0001-5713-4059
Michael H. Albert;Marie-Louise Lackner;Martin Lackner;Vincent Vatter
The Permutation Pattern Matching problem, asking whether a pattern
permutation $\pi$ is contained in a permutation $\tau$, is known to be
NP-complete. In this paper we present two polynomial time algorithms for
special cases. The first algorithm is applicable if both $\pi$ and $\tau$ are
$321$-avoiding; the second is applicable if $\pi$ and $\tau$ are skew-merged.
Both algorithms have a runtime of $O(kn)$, where $k$ is the length of $\pi$ and
$n$ the length of $\tau$.