Enumerating longest increasing subsequences and patience sorting

DOI10.1016/S0020-0190(00)00124-1zbMATH Open1338.68205DBLPjournals/ipl/BespamyatnikhS00aWikidataQ56475290 ScholiaQ56475290MaRDI QIDQ294846FDOQ294846

Authors: Sergei Bespamyatnikh, Michael Segal 

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

Recommendations

• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Longest increasing subsequences in pattern-restricted permutations
• An efficient algorithm for enumerating longest common increasing subsequences
• scientific article; zbMATH DE number 3860389
• Fast computation of a longest increasing subsequence and application
• scientific article; zbMATH DE number 6970852
• On two variants of the longest increasing subsequence problem
• scientific article; zbMATH DE number 1515819
• The longest commonly positioned increasing subsequences problem
• Longest increasing subsequences in sliding windows

zbMATH Keywords

algorithmslongest increasing subsequencevan Emde Boas tree

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Longest Increasing and Decreasing Subsequences
• Preserving order in a forest in less than logarithmic time and linear space
• On computing the length of longest increasing subsequences
• A fast algorithm for computing longest common subsequences
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem

Cited In (32)

• Title not available (Why is that?)
• Computing a longest common subsequence that is almost increasing on sequences having no repeated elements
• Insertion and sorting in a sequence of numbers minimizing the maximum sum of a contiguous subsequence
• The longest almost increasing subsequence problem with sliding windows
• Variable neighborhood algebraic differential evolution: an application to the linear ordering problem with cumulative costs
• A fast algorithm for computing a longest common increasing subsequence
• A linear space algorithm for computing a longest common increasing subsequence
• Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays
• Fast and longest rollercoasters
• The monoids of the patience sorting algorithm
• Move schedules: fast persistence computations in coarse dynamic settings
• Improvised divide and conquer approach for the LIS problem
• On-line scheduling with monotone subsequence constraints
• Subsequences in bounded ranges: matching and analysis problems
• A review of metrics on permutations for search landscape analysis
• Space-efficient algorithms for longest increasing subsequence
• Space-efficient algorithms for longest increasing subsequence
• An experimental comparison of algebraic crossover operators for permutation problems
• A geometric form for the extended patience sorting algorithm
• Co-divergence and tree topology
• Longest increasing subsequences in windows based on canonical antichain partition
• Longest increasing subsequence under persistent comparison errors
• Longest increasing subsequences in sliding windows
• Fast computation of a longest increasing subsequence and application
• Commentary on ``Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem by David Aldous and Persi Diaconis
• Restricted patience sorting and barred pattern avoidance
• FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search
• Faster algorithms for computing longest common increasing subsequences
• Efficient algorithms for finding a longest common increasing subsequence
• A diagonal-based algorithm for the longest common increasing subsequence problem
• Combinatorics of patience sorting monoids
• Finding longest increasing and common subsequences in streaming data

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

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