The computational landscape of permutation patterns

zbMath1313.05003arXiv1301.0340MaRDI QIDQ2937642

Marie-Louise Bruner, Martin Lackner

Publication date: 9 January 2015

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

zbMATH Keywords

computational complexitypattern matchingpermutation patternparameterized complexity theory

Mathematics Subject Classification ID

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

Related Items (9)

Order-preserving indexing ⋮ A fast algorithm for permutation pattern matching based on alternating runs ⋮ Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem ⋮ Parity permutation pattern matching ⋮ Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations ⋮ An \(O(n^2\log m)\)-time algorithm for the boxed-mesh permutation pattern matching problem ⋮ Unnamed Item ⋮ Finding and counting permutations via CSPs ⋮ Kernelization lower bound for permutation pattern matching

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