Parity permutation pattern matching

DOI10.1007/S00453-024-01237-0MaRDI QIDQ6586663zbMATH OpenFDO

Authors Virginia Ardévol Martínez, Florian Sikora, Stéphane Vialette

Publication date 13 August 2024

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-024-01237-0

zbMATH Keywords

fixed parameter tractabilityNP-hardnessparameterized hardnesspermutation pattern matching

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Cites work

• Classifying descents according to parity
• Combinatorics of the group of parity alternating permutations
• Faster exponential algorithm for permutation pattern matching
• Finding and counting permutations via CSPs
• Finding small patterns in permutations in linear time
• Hardness of permutation pattern matching
• scientific article; zbMATH DE number 7646025 (Why is no real title available?)
• scientific article; zbMATH DE number 7724238 (Why is no real title available?)
• On Complexity of the Subpattern Problem
• Parameterized algorithms
• Parity permutation pattern matching
• Pattern matching for 321-avoiding permutations
• Pattern matching for \(k\)-track permutations
• Pattern matching for permutations
• Patterns in permutations and words.
• Permutation pattern matching for doubly partially ordered patterns
• Permutation pattern matching in (213,231)-avoiding permutations
• The complexity of pattern matching for 321-avoiding and skew-merged permutations
• The computational landscape of permutation patterns
• Tight lower bounds for certain parameterized NP-hard problems
• Twin-width. I: Tractable FO model checking

This page was built for publication: Parity permutation pattern matching

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