Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Lackner, M., & Bruner, M.-L. (2012). A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs. In F. Fomin & P. Kaski (Eds.), Algorithm Theory – SWAT 2012 (pp. 261–270). Springer. https://doi.org/10.1007/978-3-642-31155-0_23
E104-05 - Forschungsbereich Kombinatorik und Algorithmen E192 - Institut für Logic and Computation
-
Published in:
Algorithm Theory – SWAT 2012
-
Date (published):
2012
-
Event name:
Symposium and Workshops on Algorithm Theory (SWAT)
-
Event date:
4-Jul-2012 - 6-Jul-2012
-
Event place:
Helsinki, Finnland, EU
-
Number of Pages:
10
-
Publisher:
Springer, 7357
-
Peer reviewed:
Yes
-
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).
en
Additional information:
Public link: http://link.springer.com/content/pdf/bfm%3A978-3-642-31155-0%2F1
-
Research Areas:
außerhalb der gesamtuniversitären Forschungsschwerpunkte: 100%
