On the longest upsequence problem for permutations

DOI10.1080/00207160108805049MaRDI QIDQ2731076zbMATH OpenOpenAlexFDO

Authors Erkki Mäkinen

Publication date 28 October 2001

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160108805049

zbMATH Keywords

algorithmpermutationstratified treeupsequenceYoung tableau

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial aspects of representation theory (05E10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3997796
• Fast computation of a longest increasing subsequence and application
• scientific article; zbMATH DE number 3880704
• An algorithm for the determination of longest increasing subsequence in a sequence
• scientific article; zbMATH DE number 1998299

Cites work

• Bounded ordered dictionaries in O(log log N) time and O(n) space
• Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
• Finding pattern matchings for permutations
• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Longest Increasing and Decreasing Subsequences
• Pattern matching for permutations
• Preserving order in a forest in less than logarithmic time and linear space
• Restricted permutations

Cited in

(4)

• The Preisach graph and longest increasing subsequences
• scientific article; zbMATH DE number 3880704 (Why is no real title available?)
• scientific article; zbMATH DE number 3997796 (Why is no real title available?)
• scientific article; zbMATH DE number 7559423 (Why is no real title available?)

This page was built for publication: On the longest upsequence problem for permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2731076)