Longest Common Pattern between two Permutations
<|reference_start|>Longest Common Pattern between two Permutations: 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 algorithm for general permutations whose complexity depends on the length of the longest simple permutation involved in one of our permutations.<|reference_end|>
@article{rossin2006longest,
    title={Longest Common Pattern between two Permutations},
    author={Dominique Rossin (LIAFA), Mathilde Bouvel (LIAFA)},
    journal={Algebr. Geom. Topol. 7 (2007) 829-843},
    year={2006},
    doi={10.2140/agt.2007.7.829},
    archivePrefix={arXiv},
    eprint={math/0611679},
    primaryClass={math.CO cs.DM cs.DS}
}