On the longest upsequence problem for permutations

DOI10.1080/00207160108805049zbMath0976.05002OpenAlexW2108573494MaRDI QIDQ2731076

Erkki Maekinen

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

algorithmpermutationYoung tableaustratified treeupsequence

Mathematics Subject Classification ID

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

Related Items (2)

A fast algorithm for permutation pattern matching based on alternating runs ⋮ Unnamed Item

Cites Work

• Finding pattern matchings for permutations
• Pattern matching for permutations
• 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
• Preserving order in a forest in less than logarithmic time and linear space
• Longest Increasing and Decreasing Subsequences
• Restricted permutations
• Unnamed Item
• Unnamed Item

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