Selection and Sorting in the “Restore” Model

DOI10.1137/1.9781611973402.74zbMath1421.68033OpenAlexW4254929441MaRDI QIDQ5384036

J. Ian Munro, Timothy M. Chan, 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)

Related Items

Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits, Optimal in-place suffix sorting, Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\), Frameworks for designing in-place graph algorithms, A Framework for In-place Graph Algorithms, A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon, Selection from read-only memory with limited workspace, Space efficient linear time algorithms for BFS, DFS and applications