Optimal Time Minimal Space Selection Algorithms

DOI10.1145/322261.322264MaRDI QIDQ3911405zbMATH OpenOpenAlexFDO

Authors David P. Dobkin, J. Ian Munro

Publication date 1981

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322261.322264

zbMATH Keywords

linear-time algorithmlower boundmediansorting

Mathematics Subject Classification ID

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

Cited in

(7)

• Computing the Burrows-Wheeler transform in place and in small space
• Near-optimal online multiselection in internal and external memory
• Closing a long-standing complexity gap for selection: \(V _{3}(42) = 50\)
• Learning nested concept classes with limited storage
• Deterministic cache-oblivious funnelselect
• Lazy B-trees
• External-memory priority queues with optimal insertions

This page was built for publication: Optimal Time Minimal Space Selection Algorithms

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