Upper bounds for time-space trade-offs in sorting and selection
From MaRDI portal
Publication:1101238
DOI10.1016/0022-0000(87)90002-XzbMath0642.68122OpenAlexW2053984076MaRDI QIDQ1101238
Publication date: 1987
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(87)90002-x
Related Items (31)
Optimal In-place Algorithms for Basic Graph Problems ⋮ Strictly in-place algorithms for permuting and inverting permutations ⋮ Finding the Median (Obliviously) with Bounded Space ⋮ Improved upper bounds for time-space tradeoffs for selection with limited storage ⋮ Memory-constrained algorithms for simple polygons ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ Reprint of: Memory-constrained algorithms for simple polygons ⋮ A new balanced subdivision of a simple polygon for time-space trade-off algorithms ⋮ Computing a visibility polygon using few variables ⋮ Constant work-space algorithms for facility location problems ⋮ Sorting and ranking of self-delimiting numbers with applications to tree isomorphism ⋮ A time-space tradeoff for sorting on non-oblivious machines ⋮ Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\) ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals ⋮ Space-time trade-offs for stack-based algorithms ⋮ Selection from read-only memory and sorting with minimum data movement ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ Space-efficient algorithms for longest increasing subsequence ⋮ Priority Queues and Sorting for Read-Only Data ⋮ Approximation in (Poly-) logarithmic space ⋮ Selection from read-only memory with limited workspace ⋮ Improved Space Efficient Algorithms for BFS, DFS and Applications ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Unnamed Item ⋮ Space efficient linear time algorithms for BFS, DFS and applications ⋮ Computing (and Life) Is All about Tradeoffs ⋮ A Survey on Priority Queues ⋮ Finding median in read-only memory on integer input
Cites Work
- Unnamed Item
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- Selection and sorting with limited storage
- A time-space tradeoff for sorting on non-oblivious machines
- Time bounds for selection
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
This page was built for publication: Upper bounds for time-space trade-offs in sorting and selection
