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

DOI10.1016/J.TCS.2017.02.022zbMATH Open1386.68233OpenAlexW2593271174MaRDI QIDQ1698703FDOQ1698703

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

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

zbMATH Keywords

permutation pattern matchingorder-isomorphismboxed-mesh pattern

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

• Introduction to algorithms.
• Title not available (Why is that?)
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• Pattern matching for permutations
• Boxed permutation pattern matching
• Order-preserving matching
• The computational landscape of permutation patterns
• A linear time algorithm for consecutive permutation pattern matching
• A fast algorithm for order-preserving pattern matching
• Consecutive patterns in permutations
• Avoidance of boxed mesh patterns on permutations
• Improved algorithms for the boxed-mesh permutation pattern matching problem

Cited In (2)

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

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)