An O(n^2 m)-time algorithm for the boxed-mesh permutation pattern matching problem

DOI10.1016/J.TCS.2017.02.022MaRDI QIDQ1698703zbMATH OpenOpenAlexFDO

Authors Sukhyeun Cho, Joong Chae Na, J. S. Sim

Publication date 16 February 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2017.02.022

zbMATH Keywords

permutation pattern matchingorder-isomorphismboxed-mesh pattern

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Improved algorithms for the boxed-mesh permutation pattern matching problem
• Boxed permutation pattern matching
• A linear time algorithm for consecutive permutation pattern matching
• Finding pattern matchings for permutations
• Sub-quadratic time and linear space data structures for permutation matching in binary strings

Cites work

• scientific article; zbMATH DE number 6297698 (Why is no real title available?)
• A fast algorithm for order-preserving pattern matching
• A linear time algorithm for consecutive permutation pattern matching
• Avoidance of boxed mesh patterns on permutations
• Boxed permutation pattern matching
• Consecutive patterns in permutations
• Improved algorithms for the boxed-mesh permutation pattern matching problem
• Introduction to algorithms.
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• Order-preserving matching
• Pattern matching for permutations
• The computational landscape of permutation patterns

Cited in

(2)

• Improved algorithms for the boxed-mesh permutation pattern matching problem
• Boxed permutation pattern matching

This page was built for publication: An \(O(n^2\log m)\)-time algorithm for the boxed-mesh permutation pattern matching problem

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