Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
M. Lackner, M. Bruner:
"A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs";
Vortrag: Symposium and Workshops on Algorithm Theory (SWAT),
Helsinki, Finnland;
04.07.2012
- 06.07.2012; in: "Lecture Notes of Computer Science",
F. Fomin, P. Kaski (Hrg.);
Springer,
7357
(2012),
ISBN: 978-3-642-31154-3;
S. 261
- 270.
Kurzfassung englisch:
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).
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-31155-0_23
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.