The computational landscape of permutation patterns

MaRDI QIDQ2937642zbMATH OpenFDO

Authors Marie-Louise Bruner, Martin Lackner

Publication date 9 January 2015

Full work available at URL https://arxiv.org/abs/1301.0340

zbMATH Keywords

computational complexityparameterized complexity theorypattern matchingpermutation pattern

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• On Complexity of the Subpattern Problem
• Pattern matching for permutations
• Pattern matching for permutations
• Hardness of permutation pattern matching
• Pattern matching for 321-avoiding permutations

Cited in

(11)

• An \(O(n^2\log m)\)-time algorithm for the boxed-mesh permutation pattern matching problem
• Finding and counting permutations via CSPs
• Permutation reconstruction from a few large patterns
• Kernelization lower bound for permutation pattern matching
• Improved algorithms for the boxed-mesh permutation pattern matching problem
• Order-preserving indexing
• scientific article; zbMATH DE number 5870282 (Why is no real title available?)
• Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
• scientific article; zbMATH DE number 7765381 (Why is no real title available?)
• Parity permutation pattern matching
• Parity permutation pattern matching

This page was built for publication: The computational landscape of permutation patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2937642)