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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references