32
Views
4
CrossRef citations to date
0
Altmetric
Original Articles

On the longest upsequence problem for permutations

Pages 45-53 | Received 04 Jan 2000, Published online: 19 Mar 2007
 

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.

C.R. Categories::

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].

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.