On computing the length of longest increasing subsequences

DOI10.1016/0012-365X(75)90103-XzbMath0312.68027DBLPjournals/dm/Fredman75WikidataQ56004218 ScholiaQ56004218MaRDI QIDQ1219686

Michael L. Fredman

Publication date: 1975

Published in: Discrete Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (67)

A fast algorithm for computing a longest common increasing subsequence ⋮ Enumerating longest increasing subsequences and patience sorting ⋮ Longest increasing subsequences in windows based on canonical antichain partition ⋮ Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem ⋮ On the longest increasing subsequence of a circular list ⋮ Computing the all-pairs longest chains in the plane ⋮ Hiding points in arrangements of segments ⋮ Computing the longest common almost-increasing subsequence ⋮ Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ On compressing permutations and adaptive sorting ⋮ Unnamed Item ⋮ Computing and ranking measures of presortedness ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Ruler Wrapping ⋮ Algorithms for testing occurrences of length 4 patterns in permutations ⋮ A positive fraction Erdős-Szekeres theorem and its applications ⋮ The dual diameter of triangulations ⋮ The longest commonly positioned increasing subsequences problem ⋮ Another look at the longest ascending subsequence problem ⋮ Empirical scaling of the length of the longest increasing subsequences of random walks ⋮ Powers of geometric intersection graphs and dispersion algorithms ⋮ FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Fast computation of a longest increasing subsequence and application ⋮ A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem ⋮ Faster algorithms for computing longest common increasing subsequences ⋮ The monoids of the patience sorting algorithm ⋮ Online Scheduling with Increasing Subsequence Serving Constraint ⋮ On-line Scheduling with a Monotonous Subsequence Constraint ⋮ Extracting constrained 2-interval subsets in 2-interval sets ⋮ Rollercoasters and Caterpillars ⋮ New clique and independent set algorithms for circle graphs ⋮ Tight Ω(nlgn) lower bound for finding a longest increasing subsequence ⋮ Trapezoid graphs and generalizations, geometry and algorithms ⋮ Space-efficient algorithms for longest increasing subsequence ⋮ Handling precedence constraints in scheduling problems by the sequence pair representation ⋮ Improvised divide and conquer approach for the LIS problem ⋮ Discovering distorted repeating patterns in polyphonic music through longest increasing subsequences ⋮ Estimating the Longest Increasing Sequence in Polylogarithmic Time ⋮ On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems ⋮ Trapezoid graphs and generalizations, geometry and algorithms ⋮ Independent set of intersection graphs of convex objects in 2D ⋮ How good is the information theory bound in sorting? ⋮ Computing balanced convex partitions of lines ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Finding longest increasing and common subsequences in streaming data ⋮ Unnamed Item ⋮ A note on adaptive parallel sorting ⋮ Sorting shuffled monotone sequences ⋮ Longest increasing subsequence under persistent comparison errors ⋮ Unnamed Item ⋮ Representing point sets on the plane as permutations ⋮ A diagonal-based algorithm for the longest common increasing subsequence problem ⋮ Rollercoasters: Long Sequences without Short Runs ⋮ The longest almost-increasing subsequence ⋮ Efficient algorithms for the inverse sorting problem with bound constraints under the \(l_{\infty }\)-norm and the Hamming distance ⋮ On-line scheduling with monotone subsequence constraints ⋮ Unnamed Item ⋮ The parallel stack loading problem minimizing the number of reshuffles in the retrieval stage ⋮ Computing a longest common subsequence for a set of strings ⋮ Tournaments and Semicomplete Digraphs ⋮ Fully dynamic algorithms for permutation graph coloring ⋮ Order-preserving pattern matching indeterminate strings ⋮ Computing maximum non-crossing matching in convex bipartite graphs ⋮ Efficient labelling algorithms for the maximum noncrossing matching problem ⋮ New algorithms for the LCS problem ⋮ Fast and longest rollercoasters

Cites Work

• Unnamed Item
• Unnamed Item

This page was built for publication: On computing the length of longest increasing subsequences