A fast algorithm for permutation pattern matching based on alternating runs

DOI10.1007/s00453-015-0013-yzbMath1344.68311arXiv1204.5224OpenAlexW1803235859MaRDI QIDQ300457

Martin Lackner, Marie-Louise Bruner

Publication date: 28 June 2016

Published in: Algorithmica, Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

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

zbMATH Keywords

combinatoricspattern matchingpermutation patternsfixed-parameter tractabilityparameterized complexityexponential algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Related Items (9)

A fast algorithm for permutation pattern matching based on alternating runs ⋮ A linear time algorithm for consecutive permutation pattern matching ⋮ Parity permutation pattern matching ⋮ Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Subalgebras of Solomon's descent algebra based on alternating runs ⋮ Finding and counting permutations via CSPs ⋮ Kernelization lower bound for permutation pattern matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding pattern matchings for permutations
• Pattern matching for permutations
• A fast algorithm for permutation pattern matching based on alternating runs
• Fundamentals of parameterized complexity
• A linear time algorithm for consecutive permutation pattern matching
• Exact exponential algorithms.
• Patterns in permutations and words.
• Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
• Parallel algorithms for separable permutations
• Order-preserving matching
• Probability theory. A comprehensive course.
• Parametrized complexity theory.
• On the longest upsequence problem for permutations
• The computational landscape of permutation patterns
• Longest Increasing and Decreasing Subsequences
• Longest Common Separable Pattern Among Permutations
• On Complexity of the Subpattern Problem
• Pattern Matching for 321-Avoiding Permutations
• Order-Preserving Pattern Matching with k Mismatches
• Finding small patterns in permutations in linear time
• The Covariance Matrix of Runs Up and Down
• Restricted permutations

This page was built for publication: A fast algorithm for permutation pattern matching based on alternating runs