Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers

DOI10.1007/978-3-642-45030-3_38MaRDI QIDQ2872104zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, J. Ian Munro, Venkatesh Raman

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45030-3_38

zbMATH Keywords

selectionintegersread-only memorycentroid of a treemajority finding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• Selection from read-only memory and sorting with minimum data movement
• Improved fast integer sorting in linear space
• Improved fast integer sorting in linear space
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• scientific article; zbMATH DE number 1808207
• Faster space-efficient algorithms for subset sum and k-sum
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• Selection from read-only memory with limited workspace
• Selection from read-only memory with limited workspace

Cited in

(18)

• Selection from read-only memory and sorting with minimum data movement
• The shifting sands algorithm
• Frameworks for designing in-place graph algorithms
• Rectilinear path problems in restricted memory setup
• Streaming Algorithms for Selection and Approximate Sorting
• A framework for in-place graph algorithms
• Finding median in read-only memory on integer input
• Deterministic Splitter Finding in a Stream with Constant Storage and Guarantees
• Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs
• Comparison-based time-space lower bounds for selection
• Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?
• Linear-time in-place selection in less than 3n comparisons
• Optimal In-place Algorithms for Basic Graph Problems
• Memory-Efficient Algorithms for Finding Needles in Haystacks
• Selection from read-only memory with limited workspace
• Selection from read-only memory with limited workspace
• scientific article; zbMATH DE number 1629859 (Why is no real title available?)
• Lightweight approximate selection

This page was built for publication: Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers

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