On the longest upsequence problem for permutations (Q2731076)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1625522
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the longest upsequence problem for permutations |
scientific article; zbMATH DE number 1625522 |
Statements
On the longest upsequence problem for permutations (English)
0 references
28 October 2001
0 references
algorithm
0 references
permutation
0 references
upsequence
0 references
stratified tree
0 references
Young tableau
0 references
0 references
0.8073078989982605
0 references
0.8019693493843079
0 references
Longest increasing and decreasing subsequences of a permutation of \(n\) numbers can be computed in time \(O(n\log\log n)\). This restates a result by \textit{M.-S. Chang} and \textit{F.-H. Wang} [Inf. Process. Lett. 43, No. 6, 293-295 (1992; Zbl 0768.68126)] on maximum cliques and independent sets in permutation graphs. Moreover, there is an algorithm constructing the Young tableau of a permutation in time \(O(n^{1.5}\log\log n)\).
0 references