Selection and sorting in the ``restore model

DOI10.1137/1.9781611973402.74MaRDI QIDQ5384036zbMATH OpenOpenAlexFDO

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

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973402.74

Mathematics Subject Classification ID

Searching and sorting (68P10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Selection and sorting in the ``restore model
• Selection from read-only memory and sorting with minimum data movement
• Finding median in read-only memory on integer input
• Selection from read-only memory with limited workspace
• Selection from read-only memory with limited workspace

Cited in

(10)

• A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon
• Frameworks for designing in-place graph algorithms
• A framework for in-place graph algorithms
• scientific article; zbMATH DE number 6874634 (Why is no real title available?)
• Selection and sorting in the ``restore model
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)
• Space efficient linear time algorithms for BFS, DFS and applications
• Optimal in-place suffix sorting
• Selection from read-only memory with limited workspace

This page was built for publication: Selection and sorting in the ``restore model

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