Space-efficient algorithms for longest increasing subsequence
type: Item
instance of: scholarly article
title: Space-efficient algorithms for longest increasing subsequence
zbMATH Open document ID: 1433.68632
author: Masashi Kiyomi
author: Hirotaka Ono
author: Yota Otachi
author: P. Schweitzer
author: Jun Tarui
published in: Theory of Computing Systems
publication date: 2020-04-15T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8491/
Mathematics Subject Classification ID: 68W32
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11Y55
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 7189483
zbMATH Keywords: longest increasing subsequence
zbMATH Keywords: patience sorting
zbMATH Keywords: space-efficient algorithm
MaRDI profile type: Publication
OpenAlex ID: W2913517735
cites work: A time-space trade-off for triangulations of points in the plane
cites work: Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
cites work: Priority Queues and Sorting for Read-Only Data
cites work: Depth-First Search Using $$O(n)$$ Bits
cites work: Improved Time-Space Trade-offs for Computing Voronoi Diagrams
cites work: Enumerating longest increasing subsequences and patience sorting
cites work: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
cites work: Combinatorics of patience sorting piles
cites work: Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
cites work: Multi-pass geometric algorithms
cites work: Fast computation of a longest increasing subsequence and application
cites work: Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
cites work: Space-efficient Basic Graph Algorithms
cites work: On the monotonicity of a data stream
cites work: Upper bounds for time-space trade-offs in sorting and selection
cites work: On computing the length of longest increasing subsequences
cites work: Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence
cites work: Q2934610
cites work: A fast algorithm for computing longest common subsequences
cites work: Communication Complexity
cites work: Finding longest increasing and common subsequences in streaming data
cites work: Q4598197
cites work: Selection and sorting with limited storage
cites work: A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
cites work: On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.
cites work: Tight Ω(nlgn) lower bound for finding a longest increasing subsequence
cites work: The Surprising Mathematics of Longest Increasing Subsequences
cites work: Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
cites work: Estimating the Longest Increasing Sequence in Polylogarithmic Time
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Longest Increasing and Decreasing Subsequences
cites work: Q2934612
cites work: Space-Efficient Randomized Algorithms for K-SUM
DOI: 10.1007/S00224-018-09908-6
description: scientific article; zbMATH DE number 7189483