A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs

Details A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs

2012-04-23

arxiv.org/abs/1204.5224v1

Computer Science

Data Structures and Algorithms

A short version of this paper is going to appear in the proceedings of the 13th Scandinavian Symposium and Workshops on Algori

Scientific paper

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.79^run(T)), where run(T) denotes the number of alternating runs of T. This is the first algorithm that improves upon the O*(2^n) 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).

Affiliated with

Also associated with

No associations

Rating

A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-518518