✦ LIBER ✦

Pattern matching for permutations

✍ Scribed by Prosenjit Bose; Jonathan F. Buss; Anna Lubiw

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 638 KB
Volume: 65
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00209-3

No coin nor oath required. For personal study only.

✦ Synopsis

Given a permutation

T of 1 to n, and a permutation P of 1 to k, for k < n, we wish to find a k-element subsequence of T whose elements are ordered according to the permutation P. For example, if P is ( 1,2, . . . , k), then we wish to find an increasing subsequence of length k in T; this special case was done in time O( n log log n) by Chang and Wang. We prove that the general problem is NP-complete. We give a polynomial time algorithm for the decision problem, and the corresponding counting problem, in the case that P is separablei.e., contains neither the subpattem (3,1,4,2) nor its reverse, the subpattem (2,4, 1,3).

📜 SIMILAR VOLUMES

Finding pattern matchings for permutatio

Finding pattern matchings for permutations

✍ Louis Ibarra 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 267 KB

GivenapermutationPof{l,..., k}andTof{l,..., n}, k < n, the pattern matching problem for permutations is to determine whether there is a length k subsequence of T whose elements are ordered in the same way as the elements of P. We present an 0( kn4) time and 0( kn3) space algorithm for finding a matc

Permutations with prescribed pattern

✍ L. Carlitz 📂 Article 📅 1973 🏛 John Wiley and Sons 🌐 English ⚖ 576 KB

Inverse Pattern Matching

✍ Amihood Amir; Alberto Apostolico; Moshe Lewenstein 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 181 KB

Let a textstring T of n symbols from some alphabet ⌺ and an integer mn be given. A pattern P of length m over ⌺ is sought such that P minimizes Ž . alternatively, maximizes the total number of pairwise character mismatches generated when P is compared with all m-character substrings of T. Two additi

Generating Functions for Permutations Av

Generating Functions for Permutations Avoiding a Consecutive Pattern

✍ Jeffrey Liese; Jeffrey Remmel 📂 Article 📅 2010 🏛 Springer 🌐 English ⚖ 330 KB

Spectral correspondence for point patter

Spectral correspondence for point pattern matching

✍ Marco Carcassoni; Edwin R. Hancock 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 596 KB

This paper investigates the correspondence matching of point-sets using spectral graph analysis. In particular, we are interested in the problem of how the modal analysis of point-sets can be rendered robust to contamination and drop-out. We make three contributions. First, we show how the modal str

Pattern Matching for Sets of Segments

✍ Alon Efrat; Piotr Indyk; Suresh Venkatasubramanian 📂 Article 📅 2004 🏛 Springer 🌐 English ⚖ 325 KB