Space-efficient algorithms for longest increasing subsequence
DOI10.1007/S00224-018-09908-6zbMATH Open1433.68632OpenAlexW2913517735MaRDI QIDQ1987516FDOQ1987516
Authors: Masashi Kiyomi, Hirotaka Ono, Yota Otachi, P. Schweitzer, Jun Tarui 
Publication date: 15 April 2020
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8491/
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
Analysis of algorithms (68W40) Searching and sorting (68P10) Number-theoretic algorithms; complexity (11Y16) Algorithms on strings (68W32) Calculation of integer sequences (11Y55)
Cites Work
- Longest Increasing and Decreasing Subsequences
- Relationships between nondeterministic and deterministic tape complexities
- Communication Complexity
- On computing the length of longest increasing subsequences
- Fast computation of a longest increasing subsequence and application
- Enumerating longest increasing subsequences and patience sorting
- A fast algorithm for computing longest common subsequences
- Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
- The surprising mathematics of longest increasing subsequences
- Selection and sorting with limited storage
- Upper bounds for time-space trade-offs in sorting and selection
- Multi-pass geometric algorithms
- Estimating the sortedness of a data stream
- Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
- Depth-First Search Using $$O(n)$$ Bits
- Space-efficient basic graph algorithms
- Priority queues and sorting for read-only data
- Tight Ω(nlgn) lower bound for finding a longest increasing subsequence
- Optimal time-space tradeoff for the 2D convex-hull problem
- A time-space trade-off for triangulations of points in the plane
- On space efficiency of algorithms working on structural decompositions of graphs
- Finding longest increasing and common subsequences in streaming data
- On the monotonicity of a data stream
- The communication and streaming complexity of computing the longest common and increasing subsequences
- Estimating the longest increasing sequence in polylogarithmic time
- Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
- Combinatorics of patience sorting piles
- Space-efficient randomized algorithms for \(k\)-sum
- Deterministic time-space trade-offs for \(k\)-SUM
- A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
Cited In (6)
- Streaming and query once space complexity of longest increasing subsequence
- A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem
- Space-efficient algorithms for longest increasing subsequence
- An algorithm for the determination of longest increasing subsequence in a sequence
- 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)
