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),
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.
English abstract:
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)
http://dx.doi.org/10.1007/978-3-642-31155-0_23
Created from the Publication Database of the Vienna University of Technology.