[Back]

M. Lackner:
"A Fast Algorithm for Permutation Pattern Matching";
Talk: Universität Siegen, Siegen, Deutschland; 03-22-2012.

The NP-complete Permutation Pattern Matching problem asks whether a permutation P can be matched into a permutation T. A matching is an order-preserving embedding of P into T. This problem has been studied intensively in (enumerative) combinatorics - however the computational aspect has received far less attention. Until now efficient algorithms have been proposed only for special cases of permutations. I present the first algorithm for arbitrary permutations with a runtime that is a significant improvement over the brute-force approach. This algorithm performs particularly well on permutations with few alternating runs.