On the longest upsequence problem for permutations

Abstract

Given a permutation of n numbers, its longest upsequence can be found in time O(nlog logn). Finding the longest upsequence (resp. longest downsequence) of a permutation solves the maxi- mum independent set problem (resp. the clique problem)for the corresponding permuta- tion graph. Moreover, we discuss the problem of efficiently constructing the Young tableau for a given permutation.

Keywords:

• Algorithms
• Permutation
• Upsequence
• Stratified tree
• Young tableau

C.R. Categories::

• F.2.2
• G.2.1
• E.1

^∗Work supported by the Academy of Finland (Project 35025). [email protected].

^∗Work supported by the Academy of Finland (Project 35025). [email protected].

Notes

^∗Work supported by the Academy of Finland (Project 35025). [email protected].