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

permutationalgorithmYoung tableaustratified treeupsequence

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• 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
• 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)

• scientific article; zbMATH DE number 7559423 (Why is no real title available?)
• scientific article; zbMATH DE number 3880704 (Why is no real title available?)
• The Preisach graph and longest increasing subsequences
• scientific article; zbMATH DE number 3997796 (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)