Albert, Michael H. and Lackner, Marie-Louise and Lackner, Martin and Vatter, Vincent - The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations

dmtcs:2607 - Discrete Mathematics & Theoretical Computer Science, December 21, 2016, Vol. 18 no. 2, Permutation Patterns 2015
The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations

Authors: Albert, Michael H. and Lackner, Marie-Louise and Lackner, Martin and Vatter, Vincent

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$.


Source : oai:arXiv.org:1510.06051
Volume: Vol. 18 no. 2, Permutation Patterns 2015
Section: Permutation Patterns
Published on: December 21, 2016
Submitted on: December 21, 2016
Keywords: Mathematics - Combinatorics,Computer Science - Data Structures and Algorithms,05A05, 68Q25


Share

Browsing statistics

This page has been seen 123 times.
This article's PDF has been downloaded 96 times.