Vorträge und Posterpräsentationen (ohne Tagungsband-Eintrag):
M. Lackner:
"A Fast Algorithm for Permutation Pattern Matching";
Vortrag: Universität Siegen,
Siegen, Deutschland;
22.03.2012.
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. This problem has been studied intensively in (enumerative) combinatorics - however the computational aspect has received far less attention. Until now efficient algorithms have been proposed only for special cases of permutations. I present the first algorithm for arbitrary permutations with a runtime that is a significant improvement over the brute-force approach. This algorithm performs particularly well on permutations with few alternating runs.
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.