Selection from read-only memory and sorting with minimum data movement

DOI10.1016/0304-3975(95)00225-1zbMath0872.68045OpenAlexW1990160390MaRDI QIDQ671520

Venkatesh Raman, J. Ian Munro

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00225-1

Mathematics Subject Classification ID

Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (29)

Time-space trade-offs for triangulations and Voronoi diagrams ⋮ Strictly in-place algorithms for permuting and inverting permutations ⋮ Finding the Median (Obliviously) with Bounded Space ⋮ Time-Space Trade-offs for Triangulations and Voronoi Diagrams ⋮ 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 ⋮ Reprint of: Memory-constrained algorithms for simple polygons ⋮ Computing a visibility polygon using few variables ⋮ Constant work-space algorithms for facility location problems ⋮ Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\) ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon ⋮ Prune-and-search with limited workspace ⋮ Space-time trade-offs for stack-based algorithms ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon ⋮ Asymptotically efficient in-place merging ⋮ Approximation in (Poly-) logarithmic space ⋮ In-Place Sorting ⋮ Selection from read-only memory with limited workspace ⋮ Improved Space Efficient Algorithms for BFS, DFS and Applications ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Space efficient linear time algorithms for BFS, DFS and applications ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Finding median in read-only memory on integer input ⋮ Computing the Burrows-Wheeler transform in place and in small space ⋮ Rectilinear path problems in restricted memory setup

Uses Software

• Find

Cites Work

• Upper bounds for time-space trade-offs in sorting and selection
• Selection and sorting with limited storage
• Finding the median
• Time bounds for selection
• Fast stable in-place sorting with \(O(n)\) data moves
• Sorting with minimum data movement
• Expected time bounds for selection
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Selection from read-only memory and sorting with minimum data movement