Space-efficient algorithms for longest increasing subsequence
From MaRDI portal
Publication:1987516
Recommendations
- Space-efficient algorithms for longest increasing subsequence
- A linear space algorithm for computing a longest common increasing subsequence
- Longest common subsequence in sublinear space
- Fast computation of a longest increasing subsequence and application
- An algorithm for the determination of longest increasing subsequence in a sequence
Cites work
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- A fast algorithm for computing longest common subsequences
- A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
- A time-space trade-off for triangulations of points in the plane
- Combinatorics of patience sorting piles
- Communication Complexity
- Depth-First Search Using $$O(n)$$ Bits
- Deterministic time-space trade-offs for \(k\)-SUM
- Enumerating longest increasing subsequences and patience sorting
- Estimating the longest increasing sequence in polylogarithmic time
- Estimating the sortedness of a data stream
- Fast computation of a longest increasing subsequence and application
- Finding longest increasing and common subsequences in streaming data
- Longest Increasing and Decreasing Subsequences
- Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
- Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
- Multi-pass geometric algorithms
- On computing the length of longest increasing subsequences
- On space efficiency of algorithms working on structural decompositions of graphs
- On the monotonicity of a data stream
- Optimal time-space tradeoff for the 2D convex-hull problem
- Priority queues and sorting for read-only data
- Relationships between nondeterministic and deterministic tape complexities
- Selection and sorting with limited storage
- Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
- Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
- Space-efficient basic graph algorithms
- Space-efficient randomized algorithms for \(k\)-sum
- The communication and streaming complexity of computing the longest common and increasing subsequences
- The surprising mathematics of longest increasing subsequences
- Tight Ω(nlgn) lower bound for finding a longest increasing subsequence
- Upper bounds for time-space trade-offs in sorting and selection
Cited in
(6)- Streaming and query once space complexity of longest increasing subsequence
- An algorithm for the determination of longest increasing subsequence in a sequence
- A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem
- Space-efficient algorithms for longest increasing subsequence
- Estimating the longest increasing sequence in polylogarithmic time
- Sequential dependency computation via geometric data structures
This page was built for publication: Space-efficient algorithms for longest increasing subsequence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1987516)
