Selection from read-only memory and sorting with minimum data movement
From MaRDI portal
Publication:671520
DOI10.1016/0304-3975(95)00225-1zbMATH Open0872.68045OpenAlexW1990160390MaRDI QIDQ671520FDOQ671520
Authors: J. Ian Munro, Venkatesh Raman 
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
Recommendations
- Selection from read-only memory with limited workspace
- Selection from read-only memory with limited workspace
- Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
- scientific article; zbMATH DE number 140497
- Sorting with minimum data movement
- Stable in situ sorting and minimum data movement
- Sorting and searching in the presence of memory faults (without redundancy)
- Selection in the presence of memory faults, with applications to in-place resilient sorting
- RAM-efficient external memory sorting
- RAM-efficient external memory sorting
Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Time bounds for selection
- Selection and sorting with limited storage
- Upper bounds for time-space trade-offs in sorting and selection
- Expected time bounds for selection
- Title not available (Why is that?)
- Finding the median
- Fast stable in-place sorting with \(O(n)\) data moves
- Sorting with minimum data movement
- Title not available (Why is that?)
Cited In (36)
- Finding the Median (Obliviously) with Bounded Space
- Approximation in (Poly-) logarithmic space
- A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon
- Computing a visibility polygon using few variables
- Strictly in-place algorithms for permuting and inverting permutations
- Time-space trade-offs for triangulations and Voronoi diagrams
- Time-space trade-offs for triangulations and Voronoi diagrams
- Asymptotically efficient in-place merging
- Memory-constrained algorithms for simple polygons
- Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon
- Frameworks for designing in-place graph algorithms
- Computing the Burrows-Wheeler transform in place and in small space
- Rectilinear path problems in restricted memory setup
- Improved Space Efficient Algorithms for BFS, DFS and Applications
- Finding median in read-only memory on integer input
- Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
- Sublinear-space approximation algorithms for Max \(r\)-SAT
- Stable in situ sorting and minimum data movement
- Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
- Approximation in (Poly-) Logarithmic Space
- Prune-and-search with limited workspace
- Sorting with minimum data movement
- Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)
- Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?
- Space efficient linear time algorithms for BFS, DFS and applications
- Linear-time in-place selection with \(\varepsilon \cdot n\) element moves
- Space-time trade-offs for stack-based algorithms
- Computing (and Life) Is All about Tradeoffs
- Title not available (Why is that?)
- Constant work-space algorithms for facility location problems
- In-place sorting
- Improved upper bounds for time-space tradeoffs for selection with limited storage
- Selection from read-only memory with limited workspace
- Selection from read-only memory with limited workspace
- A Framework for In-place Graph Algorithms
- Reprint of: Memory-constrained algorithms for simple polygons
Uses Software
This page was built for publication: Selection from read-only memory and sorting with minimum data movement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q671520)
