Talks and Poster Presentations (with Proceedings-Entry):
M. Lackner, M. Bruner:
"A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs";
Talk: Symposium and Workshops on Algorithm Theory (SWAT),
- 07-06-2012; in: "Lecture Notes of Computer Science",
F. Fomin, P. Kaski (ed.);
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).
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Created from the Publication Database of the Vienna University of Technology.