Space-efficient algorithms for longest increasing subsequence

DOI10.1007/s00224-018-09908-6zbMath1433.68632MaRDI 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/

zbMATH Keywords

longest increasing subsequence; space-efficient algorithm; patience sorting

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68P10: Searching and sorting

11Y16: Number-theoretic algorithms; complexity

68W32: Algorithms on strings

11Y55: Calculation of integer sequences

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