Parity permutation pattern matching

DOI10.1007/s00453-024-01237-0MaRDI QIDQ6586663

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

Publication date: 13 August 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

fixed parameter tractabilityNP-hardnesspermutation pattern matchingparameterized hardness

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pattern matching for permutations
• A fast algorithm for permutation pattern matching based on alternating runs
• Patterns in permutations and words.
• Pattern matching for \(k\)-track permutations
• Finding and counting permutations via CSPs
• Combinatorics of the group of parity alternating permutations
• Classifying descents according to parity
• Tight lower bounds for certain parameterized NP-hard problems
• The computational landscape of permutation patterns
• On Complexity of the Subpattern Problem
• Pattern Matching for 321-Avoiding Permutations
• The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations
• Hardness of Permutation Pattern Matching
• Twin-width I: Tractable FO Model Checking
• Finding small patterns in permutations in linear time
• Parameterized Algorithms
• Parity permutation pattern matching
• Permutation pattern matching for doubly partially ordered patterns
• Faster exponential algorithm for permutation pattern matching

This page was built for publication: Parity permutation pattern matching