Boxed Permutation Pattern Matching.

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

doi:10.4230/LIPIcs.CPM.2016.20

Boxed Permutation Pattern Matching.

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

Department of Applied Mathematics and Computer Science

University of Haifa

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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(n³) time. Cho et al. [CPM 2015] gave an O(n²m) time algorithm and improved it to O(n² logm). In this paper we present a solution that uses only O(n²) time. In general, there are instances where the output size is Ω(n²) 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 language	English
Title of host publication	Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Publication date	2016
Pages	1-11
Article number	20
DOIs	https://doi.org/10.4230/LIPIcs.CPM.2016.20
Publication status	Published - 2016
Event	27th Annual Symposium on Combinatorial Pattern Matching - Tel Aviv, Israel Duration: 27 Jun 2016 → 29 Jun 2016 Conference number: 27 https://faculty.biu.ac.il/~cpm2016/index.html

Conference

Conference	27th Annual Symposium on Combinatorial Pattern Matching
Number	27
Country/Territory	Israel
City	Tel Aviv
Period	27/06/2016 → 29/06/2016
Internet address	https://faculty.biu.ac.il/~cpm2016/index.html

Series	Leibniz International Proceedings in Informatics
ISSN	1868-8969

Keywords

Permutation
Subsequence
Pattern Matching
Order Preserving
Boxed Mesh Pattern

Access to Document

10.4230/LIPIcs.CPM.2016.20

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{a28f33d8cc254036998f51b216f7ac95,

title = "Boxed Permutation Pattern Matching.",

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.",

keywords = "Permutation, Subsequence, Pattern Matching, Order Preserving, Boxed Mesh Pattern",

author = "Mika Amit and Philip Bille and Cording, \{Patrick Hagge\} and G{\o}rtz, \{Inge Li\} and Vildh{\o}j, \{Hjalte Wedel\}",

year = "2016",

doi = "10.4230/LIPIcs.CPM.2016.20",

language = "English",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "1--11",

booktitle = "Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)",

note = "27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016 ; Conference date: 27-06-2016 Through 29-06-2016",

url = "https://faculty.biu.ac.il/\textasciitilde{}cpm2016/index.html",

}

Amit, M, Bille, P, Cording, PH, Gørtz, IL & Vildhøj, HW 2016, Boxed Permutation Pattern Matching. in Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)., 20, Leibniz International Proceedings in Informatics, pp. 1-11, 27th Annual Symposium on Combinatorial Pattern Matching, Tel Aviv, Israel, 27/06/2016. https://doi.org/10.4230/LIPIcs.CPM.2016.20

TY - GEN

T1 - Boxed Permutation Pattern Matching.

AU - Amit, Mika

AU - Bille, Philip

AU - Cording, Patrick Hagge

AU - Gørtz, Inge Li

AU - Vildhøj, Hjalte Wedel

N1 - Conference code: 27

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

KW - Permutation

KW - Subsequence

KW - Pattern Matching

KW - Order Preserving

KW - Boxed Mesh Pattern

U2 - 10.4230/LIPIcs.CPM.2016.20

DO - 10.4230/LIPIcs.CPM.2016.20

M3 - Article in proceedings

T3 - Leibniz International Proceedings in Informatics

SP - 1

EP - 11

BT - Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

T2 - 27th Annual Symposium on Combinatorial Pattern Matching

Y2 - 27 June 2016 through 29 June 2016

ER -

Boxed Permutation Pattern Matching.

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this