Parallelism in Comparison Problems
From MaRDI portal
Publication:4069777
DOI10.1137/0204030zbMath0311.68033OpenAlexW2089062581MaRDI QIDQ4069777
Publication date: 1975
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0204030
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) General topics in the theory of software (68N01) Algorithms in computer science (68W99)
Related Items (76)
Comparison-based interactive collaborative filtering ⋮ On the complexity and approximability of budget-constrained minimum cost flows ⋮ Extremal polygon containment problems ⋮ Routing, merging, and sorting on parallel models of computation ⋮ Selecting distances in the plane ⋮ Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ Almost fully-parallel parentheses matching ⋮ Heap construction in the parallel comparison tree model ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs ⋮ A time-randomness tradeoff for selection in parallel ⋮ Finding all periods and initial palindromes of a string in parallel ⋮ Comparison-Based Interactive Collaborative Filtering ⋮ A parallel algorithm for bisection width in trees ⋮ Parallel construction of a suffix tree with applications ⋮ An O(log n) time parallel algorithm for triangulating a set of points in the plane ⋮ SORTING AND SELECTION ON DISTRIBUTED MEMORY BUS COMPUTERS ⋮ FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH ⋮ An optimally efficient selection algorithm ⋮ A unified \(O(\log N)\) and optimal sorting vector algorithm ⋮ Sweep methods for parallel computational geometry ⋮ Parallel construction of binary trees with near optimal weighted path length ⋮ Exploiting storage redundancy to speed up randomized shared memory simulations ⋮ A parallel sorting scheme whose basic operation sortsN elements ⋮ Fast deterministic selection on mesh-connected processor arrays ⋮ Parallel computational geometry ⋮ L-infinity interdistance selection by parametric search ⋮ Sorting Short Keys in Circuits of Size ${o(n \log n)}$ ⋮ Optimal parallel selection has complexity O(log log N) ⋮ Parametric search made practical ⋮ The average performance of a parallel stable mariage algorithm ⋮ All Nearest Smallers Made Simple ⋮ Optimal parallel algorithms for proximate points, with applications ⋮ Conservative algorithms for parallel and sequential integer sorting ⋮ Exact learning of multitrees and almost-trees using path queries ⋮ Constant time parallel sorting: An empirical view. ⋮ Unnamed Item ⋮ New Upper Bounds on Continuous Tree Edge-Partition Problem ⋮ Prefix graphs and their applications ⋮ A complexity theory of efficient parallel algorithms ⋮ Parallel selection ⋮ A parallel computing framework for big data ⋮ Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm ⋮ Linear approximation of simple objects ⋮ Optimal randomized parallel algorithms for computational geometry ⋮ Three-regular path pairable graphs ⋮ Finding effective ``Force targets for two-dimensional, multifinger frictional grips ⋮ Finding an Unknown Acyclic Orientation of a Given Graph ⋮ Approximating Huffman codes in parallel ⋮ Efficient parallel algorithms for computing all pair shortest paths in directed graphs ⋮ Efficient dynamic range minimum query ⋮ Computing with Spikes: The Advantage of Fine-Grained Timing ⋮ Diameter, width, closest line pair, and parametric searching ⋮ Approximate parametric searching ⋮ Parallel searching of multidimensional cubes ⋮ A faster parallel algorithm for a matrix searching problem ⋮ Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\). ⋮ Randomized range-maxima in nearly-constant parallel time ⋮ A faster parallel algorithm for a matrix searching problem ⋮ Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory ⋮ The average-case parallel complexity of sorting ⋮ Parallel algorithms for merging and sorting ⋮ A near-linear algorithm for the planar segment-center problem ⋮ A nearly optimal deterministic parallel Voronoi diagram algorithm ⋮ Scalable algorithms for the mesh with buses: merging, sorting and selection ⋮ PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ A new parallel sorting algorithm based upon min-mid-max operations ⋮ Locating two obnoxious facilities using the weighted maximin criterion ⋮ A parallel median algorithm ⋮ Optimal parallel construction of heaps ⋮ Parallel comparison merging of many-ordered lists ⋮ Parallel comparison algorithms for approximation problems ⋮ An incremental and parametrical algorithm for convex-concave fractional programming with a single constraint ⋮ Sorting and Merging in Rounds ⋮ Lower bounds on parallel algorithms for finding the first maximal independent set
This page was built for publication: Parallelism in Comparison Problems
