Back to Search
Start Over
The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations
- Source :
- Discrete Mathematics & Theoretical Computer Science, Vol. 18 no. 2, Permutation Patterns 2015, Permutation Patterns (December 21, 2016) dmtcs:1308
- Publication Year :
- 2015
-
Abstract
- 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$.
Details
- Database :
- arXiv
- Journal :
- Discrete Mathematics & Theoretical Computer Science, Vol. 18 no. 2, Permutation Patterns 2015, Permutation Patterns (December 21, 2016) dmtcs:1308
- Publication Type :
- Report
- Accession number :
- edsarx.1510.06051
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.46298/dmtcs.1308