On computing the length of longest increasing subsequences
From MaRDI portal
Publication:1219686
DOI10.1016/0012-365X(75)90103-XzbMath0312.68027WikidataQ56004218 ScholiaQ56004218MaRDI QIDQ1219686
Publication date: 1975
Published in: Discrete Mathematics (Search for Journal in Brave)
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
This page was built for publication: On computing the length of longest increasing subsequences
