On the longest upsequence problem for permutations

Given a permutation of n numbers, its longest upsequence can be found in ti me O(n log log n). Finding the longest upsequence (resp. longest downsequen ce) of a permutation solves the maximum independent set problem (resp. the clique problem) for the corresponding permutation graph. Moreover, we discu ss the problem of efficiently constructing the Young tableau for a given pe rmutation.