Selection from read-only memory with limited workspace

DOI10.1016/j.tcs.2014.06.012zbMath1360.68379OpenAlexW1828011784MaRDI QIDQ744087

Jyrki Katajainen, Daniel Dahl Juhl, Amr Elmasry, 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) Searching and sorting (68P10) Data structures (68P05)

Related Items

Optimal In-place Algorithms for Basic Graph Problems, Space-efficient Euler partition and bipartite edge coloring, Constant work-space algorithms for facility location problems, Frameworks for designing in-place graph algorithms, A Framework for In-place Graph Algorithms, Space efficient linear time algorithms for BFS, DFS and applications

Cites Work

• Selection from read-only memory and sorting with minimum data movement
• Upper bounds for time-space trade-offs in sorting and selection
• Selection and sorting with limited storage
• Sorting multisets stably in minimum space
• Time bounds for selection
• Optimal lower bounds for rank and select indexes
• Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
• Wavelet Trees for All
• Comparison-based time-space lower bounds for selection
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Priority Queues and Sorting for Read-Only Data
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Selection and Sorting in the “Restore” Model
• Unnamed Item
• Unnamed Item
• Unnamed Item