Enumerating longest increasing subsequences and patience sorting

DOI10.1016/S0020-0190(00)00124-1zbMath1338.68205DBLPjournals/ipl/BespamyatnikhS00aWikidataQ56475290 ScholiaQ56475290MaRDI QIDQ294846

Michael Segal, Sergei Bespamyatnikh

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019000001241?np=y

zbMATH Keywords

algorithmslongest increasing subsequencevan Emde Boas tree

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Algorithms on strings (68W32)

Related Items (25)

A fast algorithm for computing a longest common increasing subsequence ⋮ Longest increasing subsequences in sliding windows ⋮ Longest increasing subsequences in windows based on canonical antichain partition ⋮ A linear space algorithm for computing a longest common increasing subsequence ⋮ A review of metrics on permutations for search landscape analysis ⋮ Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ Computing a longest common subsequence that is almost increasing on sequences having no repeated elements ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search ⋮ Fast computation of a longest increasing subsequence and application ⋮ Faster algorithms for computing longest common increasing subsequences ⋮ An Experimental Comparison of Algebraic Crossover Operators for Permutation Problems ⋮ Space-efficient algorithms for longest increasing subsequence ⋮ Improvised divide and conquer approach for the LIS problem ⋮ Variable neighborhood algebraic differential evolution: an application to the linear ordering problem with cumulative costs ⋮ Finding longest increasing and common subsequences in streaming data ⋮ Unnamed Item ⋮ Longest increasing subsequence under persistent comparison errors ⋮ Efficient algorithms for finding a longest common increasing subsequence ⋮ The longest almost increasing subsequence problem with sliding windows ⋮ Move schedules: fast persistence computations in coarse dynamic settings ⋮ A diagonal-based algorithm for the longest common increasing subsequence problem ⋮ Co-divergence and tree topology ⋮ On-line scheduling with monotone subsequence constraints ⋮ Fast and longest rollercoasters

Cites Work

• Unnamed Item
• On computing the length of longest increasing subsequences
• Preserving order in a forest in less than logarithmic time and linear space
• Longest Increasing and Decreasing Subsequences
• A fast algorithm for computing longest common subsequences
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem

This page was built for publication: Enumerating longest increasing subsequences and patience sorting