Permutation Pattern matching in (213, 231)-avoiding permutations
Given permutations σ of size k and π of size n with k < n, the permutation pattern matching problem is to decide whether σ occurs in π as an order-isomorphic subsequence. We give a linear-time algorithm in case both π and σ avoid the two size-3 permutations 213 and 231. For the special case where...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2017-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/1329/pdf |
| Summary: | Given permutations σ of size k and π of size n with k < n, the permutation pattern matching problem is to decide whether σ occurs in π as an order-isomorphic subsequence. We give a linear-time algorithm in case both π and σ avoid the two size-3 permutations 213 and 231. For the special case where only σ avoids 213 and 231, we present a O(max(kn 2 , n 2 log log n)-time algorithm. We extend our research to bivincular patterns that avoid 213 and 231 and present a O(kn 4)-time algorithm. Finally we look at the related problem of the longest subsequence which avoids 213 and 231. |
|---|---|
| ISSN: | 1365-8050 |