๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Finding pattern matchings for permutations

โœ Scribed by Louis Ibarra

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
267 KB
Volume
61
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 match of P into T or determining that no match exists, given that P is separable,

i.e. contains neither (2,4,1,3) nor (3,1,4,2) as a subpattem. @

๐Ÿ“œ SIMILAR VOLUMES

Pattern matching for permutations
Pattern matching for permutations
โœ Prosenjit Bose; Jonathan F. Buss; Anna Lubiw ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 638 KB

## 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 specia

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