DOAJ Open Access 2017

Permutation Pattern matching in (213, 231)-avoiding permutations

Both Neou Romeo Rizzi Stéphane Vialette

Lihat Sumber DOI

Abstrak

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.

Topik & Kata Kunci

Mathematics

Penulis (3)

Both Neou

Romeo Rizzi

Stéphane Vialette

Format Sitasi

APA MLA BibTeX

Neou, B., Rizzi, R., Vialette, S. (2017). Permutation Pattern matching in (213, 231)-avoiding permutations. https://doi.org/10.46298/dmtcs.1329

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.1329

Informasi Jurnal

Tahun Terbit: 2017
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.1329
Akses: Open Access ✓