Longest Common Pattern between two Permutations

Dominique Rossin, Mathilde Bouvel

In this paper, we give a polynomial (O(n^8)) algorithm for finding a longest common pattern between two permutations of size n given that one is separable. We also give an algorith…