The complexity of pattern matching for 321-avoiding and skew-merged permutations

MaRDI QIDQ4557004zbMATH OpenFDO

Authors Marie-Louise Lackner, Martin Lackner, Michael Albert, Vincent Vatter

Publication date 28 November 2018

Full work available at URL https://arxiv.org/abs/1510.06051, https://dmtcs.episciences.org/2607/pdf

zbMATH Keywords

algorithmscombinatoricscomputer sciencedata structurespermutation classpermutation pattern

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms on strings (68W32)

Abstract: The Permutation Pattern Matching problem, asking whether a pattern permutation $pi$ is contained in a permutation $au$, 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 $au$ are $321$-avoiding; the second is applicable if $pi$ and $au$ are skew-merged. Both algorithms have a runtime of $O(kn)$, where $k$ is the length of $pi$ and $n$ the length of $au$.

Recommendations

• Pattern matching for 321-avoiding permutations
• Permutation pattern matching in (213,231)-avoiding permutations
• Hardness of permutation pattern matching
• Pattern matching for \(k\)-track permutations
• Pattern matching for permutations

Cited in

(13)

• Pattern matching for \(k\)-track permutations
• Finding and counting permutations via CSPs
• Rationality for subclasses of 321-avoiding permutations
• Prolific permutations
• On permutations avoiding partially ordered patterns defined by bipartite graphs
• Pattern matching for 321-avoiding permutations
• Permutation pattern matching in (213,231)-avoiding permutations
• Hardness of permutation pattern matching
• Labelled well-quasi-order for permutation classes
• Two examples of Wilf-collapse
• 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 complexity of pattern matching for 321-avoiding and skew-merged permutations

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