Conference paper
Boxed Permutation Pattern Matching
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.
| Language: | English |
|---|---|
| Year: | 2016 |
| Pages: | 1-11 |
| Proceedings: | 27th Annual Symposium on Combinatorial Pattern MatchingAnnual Symposium on Combinatorial Pattern Matching |
| Series: | Leibniz International Proceedings in Informatics |
| ISSN: | 18688969 |
| Types: | Conference paper |
| DOI: | 10.4230/LIPIcs.CPM.2016.20 |
| ORCIDs: | Bille, Philip and Gørtz, Inge Li |
