M. Lackner, M. Bruner:

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

Talk: Symposium and Workshops on Algorithm Theory (SWAT), Helsinki, Finnland; 07-04-2012 - 07-06-2012; in: "Lecture Notes of Computer Science", F. Fomin, P. Kaski (ed.); Springer, 7357 (2012), ISBN: 978-3-642-31154-3; 261 - 270.

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. We present a fixed-parameter

algorithm solving this problem with an exponential worst-case runtime of O∗(1.79run(T)), where run(T) denotes the number of alternating runs of T. This is the first algorithm that improves upon the O∗(2n) runtime required by brute-force search without imposing restrictions on P and T. Furthermore we prove that - under standard complexity theoretic assumptions - such a fixed-parameter tractability result is not possible for run(P).

http://dx.doi.org/10.1007/978-3-642-31155-0_23

Created from the Publication Database of the Vienna University of Technology.