The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations
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$-avoid...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2016-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/1308/pdf |
| Summary: | 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$. |
|---|---|
| ISSN: | 1365-8050 |