Selection from read-only memory with limited workspace

DOI10.1016/J.TCS.2014.06.012MaRDI QIDQ744087zbMATHOpenAlexFDO

Authors Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, Srinivasa Rao Satti

Publication date 6 October 2014

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

Full work available at URL https://doi.org/10.1016/j.tcs.2014.06.012

zbMATH Keywords

selection algorithmbit vectormulti-pass streamingrandom-access machineread-only memorywavelet stack

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• Selection from read-only memory with limited workspace
• Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• scientific article; zbMATH DE number 1383709
• Selection from read-only memory and sorting with minimum data movement

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 1383709 (Why is no real title available?)
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• Comparison-based time-space lower bounds for selection
• Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
• Introduction to algorithms.
• Optimal lower bounds for rank and select indexes
• Priority queues and sorting for read-only data
• Selection and sorting in the ``restore model
• Selection and sorting with limited storage
• Selection from read-only memory and sorting with minimum data movement
• Sorting multisets stably in minimum space
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Time bounds for selection
• Upper bounds for time-space trade-offs in sorting and selection
• Wavelet trees for all

Cited in

(18)

• Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
• Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?
• Selection and sorting in the ``restore model
• Selection from read-only memory with limited workspace
• A framework for in-place graph algorithms
• scientific article; zbMATH DE number 4062610 (Why is no real title available?)
• Selection and sorting in the ``restore model
• Space-efficient Euler partition and bipartite edge coloring
• Space efficient linear time algorithms for BFS, DFS and applications
• Dynamic online multiselection in internal and external memory
• A nearly optimal randomized algorithm for explorable heap selection
• Optimal In-place Algorithms for Basic Graph Problems
• Constant work-space algorithms for facility location problems
• Frameworks for designing in-place graph algorithms
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• Selection from read-only memory and sorting with minimum data movement
• Finding median in read-only memory on integer input
• Prune-and-search with limited workspace

This page was built for publication: Selection from read-only memory with limited workspace

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744087)