Space-efficient algorithms for longest increasing subsequence
From MaRDI portal
Publication:1987516
DOI10.1007/s00224-018-09908-6zbMath1433.68632OpenAlexW2913517735MaRDI QIDQ1987516
Pascal Schweitzer, Hirotaka Ono, Jun Tarui, Yota Otachi, Masashi Kiyomi
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/
Analysis of algorithms (68W40) Searching and sorting (68P10) Number-theoretic algorithms; complexity (11Y16) Algorithms on strings (68W32) Calculation of integer sequences (11Y55)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Enumerating longest increasing subsequences and patience sorting
- Multi-pass geometric algorithms
- Upper bounds for time-space trade-offs in sorting and selection
- Selection and sorting with limited storage
- On computing the length of longest increasing subsequences
- On the monotonicity of a data stream
- Fast computation of a longest increasing subsequence and application
- A time-space trade-off for triangulations of points in the plane
- Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
- Finding longest increasing and common subsequences in streaming data
- Relationships between nondeterministic and deterministic tape complexities
- Combinatorics of patience sorting piles
- Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
- Space-Efficient Randomized Algorithms for K-SUM
- The Surprising Mathematics of Longest Increasing Subsequences
- Depth-First Search Using $$O(n)$$ Bits
- Space-efficient Basic Graph Algorithms
- Longest Increasing and Decreasing Subsequences
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- A fast algorithm for computing longest common subsequences
- Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
- Tight Ω(nlgn) lower bound for finding a longest increasing subsequence
- On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.
- Improved Time-Space Trade-offs for Computing Voronoi Diagrams
- Communication Complexity
- Priority Queues and Sorting for Read-Only Data
- A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
- Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence
- Estimating the Longest Increasing Sequence in Polylogarithmic Time
- Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
This page was built for publication: Space-efficient algorithms for longest increasing subsequence
