Pattern matching for 321-avoiding permutations

Abstract: Given permutations

s i g m a i n S_{k}

and

p i i n S_{n}

with

k < n

, the emph{pattern matching} problem is to decide whether

p i

matches

s i g m a

as an order-isomorphic subsequence. We give a linear-time algorithm in case both

p i

and

s i g m a

avoid the two size-

3

permutations

213

and

231

. For the special case where only

s i g m a

avoids

213

and

231

, we present a

O (m a x (k n^{2}, n^{2} l o g (l o g (n)))

time algorithm. We extend our research to bivincular patterns that avoid

213

and

231

and present a

O (k n^{4})

time algorithm. Finally we look at the related problem of the longest subsequence which avoids

213

and

231

.

Recommendations

Cited In (20)

This page was built for publication: Pattern matching for 321-avoiding permutations