The computational landscape of permutation patterns
arXiv:1301.0340
Abstract
In the last years, different types of patterns in permutations have been studied: vincular, bivincular and mesh patterns, just to name a few. Every type of permutation pattern naturally defines a corresponding computational problem: Given a pattern P and a permutation T (the text), is P contained in T? In this paper we draw a map of the computational landscape of permutation pattern matching with different types of patterns. We provide a classical complexity analysis and investigate the impact of the pattern length on the computational hardness. Furthermore, we highlight several directions in which the study of computational aspects of permutation patterns could evolve.
arXiv comment23 pages, to appear in Journal of Pure and Applied Mathematics, Special Issue for Permutation Patterns 2012
References in corpus (5)
- (2+2)-free posets, ascent sequences and pattern avoiding permutations
- Model-Checking Problems as a Basis for Parameterized Intractability
- Describing West-3-stack-sortable permutations with permutation patterns
- A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs
- Algorithms for discovering and proving theorems about permutation patterns