The computational landscape of permutation patterns

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.

23 pages, to appear in Journal of Pure and Applied Mathematics, Special Issue for Permutation Patterns 2012

References in corpus (3)

• 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

Cited by in corpus (3)

• Counting Small Permutation Patterns
• Faster and simpler algorithms for finding large patterns in permutations
• Kernelization lower bound for Permutation Pattern Matching