Selection and sorting in the ``restore model

DOI10.1137/1.9781611973402.74zbMATH Open1421.68033OpenAlexW4254929441MaRDI QIDQ5384036FDOQ5384036

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

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

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• 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)