Selection and sorting with limited storage
From MaRDI portal
Publication:1143174
DOI10.1016/0304-3975(80)90061-4zbMath0441.68067DBLPjournals/tcs/MunroP80OpenAlexW1983266860WikidataQ59795779 ScholiaQ59795779MaRDI QIDQ1143174
J. Ian Munro, Michael S. Paterson
Publication date: 1980
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/46321/1/WRAP_Munro_cs-rr-024.pdf
Related Items (80)
On finding common neighborhoods in massive graphs. ⋮ Time-space trade-offs for triangulations and Voronoi diagrams ⋮ The Online Space Complexity of Probabilistic Languages ⋮ Optimal In-place Algorithms for Basic Graph Problems ⋮ Strictly in-place algorithms for permuting and inverting permutations ⋮ Real-time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components ⋮ Finding the Median (Obliviously) with Bounded Space ⋮ Time-Space Trade-offs for Triangulations and Voronoi Diagrams ⋮ Tight lower bounds for query processing on streaming and external memory data ⋮ Improved upper bounds for time-space tradeoffs for selection with limited storage ⋮ Unnamed Item ⋮ The complexity of mean payoff games on graphs ⋮ Monitoring networked applications with incremental quantile estimation ⋮ An improved algorithm for finding the median distributively ⋮ Upper bounds for time-space trade-offs in sorting and selection ⋮ GEOMETRIC STREAMING ALGORITHM WITH A SORTING PRIMITIVE ⋮ Memory-constrained algorithms for simple polygons ⋮ Approximate sorting of data streams with limited storage ⋮ Distributed algorithms for selection in sets ⋮ Estimating extreme tail risk measures with generalized Pareto distribution ⋮ Space-efficient vertex separators for treewidth ⋮ Streaming algorithms for multitasking scheduling with shared processing ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Graph Connectivity in Log Steps Using Label Propagation ⋮ Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ Indexing for summary queries ⋮ Reprint of: Memory-constrained algorithms for simple polygons ⋮ Randomized algorithms for tracking distributed count, frequencies, and ranks ⋮ Computing a visibility polygon using few variables ⋮ Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity ⋮ Joint tracking of multiple quantiles through conditional quantiles ⋮ Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS ⋮ A nearly optimal randomized algorithm for explorable heap selection ⋮ Constant work-space algorithms for facility location problems ⋮ Adapting parallel algorithms to the W-stream model, with applications to graph problems ⋮ Unnamed Item ⋮ Lightweight data indexing and compression in external memory ⋮ A time-space tradeoff for sorting on non-oblivious machines ⋮ Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\) ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ Multiple Pass Streaming Algorithms for Learning Mixtures of Distributions in ${\mathbb R}^d$ ⋮ Sleeping on the job: energy-efficient and robust broadcast for radio networks ⋮ Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals ⋮ Learning nested concept classes with limited storage ⋮ Streaming techniques and data aggregation in networks of tiny artefacts ⋮ A Modular CDF Approach for the Approximation of Percentiles ⋮ Competitive analysis of maintaining frequent items of a stream ⋮ EFFICIENT ALGORITHMS FOR SELECTION AND SORTING OF LARGE DISTRIBUTED FILES ON DE BRUIJN AND HYPERCUBE STRUCTURES ⋮ Space-efficient biconnected components and recognition of outerplanar graphs ⋮ Space-time trade-offs for stack-based algorithms ⋮ Matching nuts and bolts faster ⋮ Selection from read-only memory and sorting with minimum data movement ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ The Hardness of Median in the Synchronized Bit Communication Model ⋮ Space-efficient algorithms for longest increasing subsequence ⋮ Matching nuts and bolts faster ⋮ Best-order streaming model ⋮ Priority Queues and Sorting for Read-Only Data ⋮ Sorting streamed multisets ⋮ Unnamed Item ⋮ Quantile regression under memory constraint ⋮ Approximation in (Poly-) logarithmic space ⋮ Regular Programming for Quantitative Properties of Data Streams ⋮ Streaming Algorithms for Selection and Approximate Sorting ⋮ Selection from read-only memory with limited workspace ⋮ COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING ⋮ Multiple pass streaming algorithms for learning mixtures of distributions in \(\mathbb R^d\) ⋮ Improved Space Efficient Algorithms for BFS, DFS and Applications ⋮ On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy ⋮ On the Value of Multiple Read/Write Streams for Data Compression ⋮ Asymmetric scale functions for t-digests ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Space efficient linear time algorithms for BFS, DFS and applications ⋮ Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50 ⋮ Frugal Streaming for Estimating Quantiles ⋮ Computing (and Life) Is All about Tradeoffs ⋮ A Survey on Priority Queues ⋮ Unnamed Item ⋮ Finding median in read-only memory on integer input
Cites Work
This page was built for publication: Selection and sorting with limited storage
