M. Bruner, M. Lackner:

"A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs";

Algorithmica (online),online(2015), 34 S.

The NP-complete Permutation Pattern Matching problem asks whether a k-permutation P is contained in a n-permutation T as a pattern. This is the case if there exists an order-preserving embedding of P into T. In this paper, we present a fixed-parameter algorithm solving this problem with a worst-case runtime of O(1.79 run(T) ⋅n⋅k) , where run(T) denotes the number of alternating runs of T. This algorithm is particularly well-suited for instances where T has few runs, i.e., few ups and downs. Moreover, since run(T)<n , this can be seen as a O(1.79 n ⋅n⋅k) algorithm which is the first to beat the exponential 2 n runtime of brute-force search. Furthermore, we prove that under standard complexity theoretic assumptions such a fixed-parameter tractability result is not possible for run(P) .

Permutation patterns - Parameterized complexity - Pattern matching - Fixed-parameter tractability - Exponential algorithms - Combinatorics

Projektleitung Stefan Woltran:

START

Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.