Boxed Permutation Pattern Matching.

Mika Amit, Philip Bille, Patrick Hagge Cording, Inge Li Gørtz, Hjalte Wedel Vildhøj

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Given permutations T and P of length n and m, respectively, the Permutation Pattern Matching problem asks to find all m-length subsequences of T that are order-isomorphic to P. This problem has a wide range of applications but is known to be NP-hard. In this paper, we study the special case, where the goal is to only find the boxed subsequences of T that are order-isomorphic to P. This problem was introduced by Bruner and Lackner who showed that it can be solved in O(n3) time. Cho et al. [CPM 2015] gave an O(n2m) time algorithm and improved it to O(n2 logm). In this paper we present a solution that uses only O(n2) time. In general, there are instances where the output size is Ω(n2) and hence our bound is optimal. To achieve our results, we introduce several new ideas including a novel reduction to 2D offline dominance counting. Our algorithm is surprisingly simple and straightforward to implement.
Original languageEnglish
Title of host publicationProceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Publication date2016
Pages1-11
Article number20
DOIs
Publication statusPublished - 2016
Event27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) - Tel Aviv, Israel
Duration: 27 Jun 201629 Jun 2016
Conference number: 27
https://faculty.biu.ac.il/~cpm2016/index.html

Conference

Conference27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Number27
CountryIsrael
CityTel Aviv
Period27/06/201629/06/2016
Internet address
SeriesLeibniz International Proceedings in Informatics
ISSN1868-8969

Keywords

  • Permutation
  • Subsequence
  • Pattern Matching
  • Order Preserving
  • Boxed Mesh Pattern

Fingerprint Dive into the research topics of 'Boxed Permutation Pattern Matching.'. Together they form a unique fingerprint.

Cite this