Boxed Permutation Pattern Matching.

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2016

DOI

View graph of relations

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
StatePublished - 2016
Event27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) - Tel Aviv, Israel

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
CitationsWeb of Science® Times Cited: No match on DOI

    Keywords

  • Permutation, Subsequence, Pattern Matching, Order Preserving, Boxed Mesh Pattern
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

ID: 127197468