Finding the maximum, merging, and sorting in a parallel computation model
From MaRDI portal
Publication:3906428
DOI10.1016/0196-6774(81)90010-9zbMath0456.68062OpenAlexW2087489294MaRDI QIDQ3906428
Publication date: 1981
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(81)90010-9
Related Items (83)
Finding level-ancestors in trees ⋮ Routing, merging, and sorting on parallel models of computation ⋮ Unbounded fan-in circuits and associative functions ⋮ Selecting distances in the plane ⋮ A faster parallel algorithm for \(k\)-connectivity ⋮ Transforming comparison model lower bounds to the parallel-random-access-machine ⋮ PROCEDURES FOR COMPUTING THE MAXIMUM WITH DNA ⋮ Prallel algorithms for analyzing activity networks ⋮ Almost fully-parallel parentheses matching ⋮ How hard is to compute the edit distance ⋮ Separation and lower bounds for ROM and nondeterministic models of parallel computation ⋮ Perfectly Load-Balanced, Stable, Synchronization-Free Parallel Merge ⋮ Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs ⋮ An optimal speed-up parallel algorithm for triangulating simplicial point sets in space ⋮ On the time required to sum n semigroup elements on a parallel machine with simultaneous writes ⋮ Fast parallel graph searching with applications ⋮ A parallel algorithm for bisection width in trees ⋮ Simulations among concurrent-write PRAMs ⋮ Parallel construction of a suffix tree with applications ⋮ Parallel computation with threshold functions ⋮ An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits ⋮ A parallel bucket sort ⋮ A linear-processor algorithm for depth-first search in planar graphs ⋮ A parallel algorithm for recognizing unordered depth-first search ⋮ A parallel sorting scheme whose basic operation sortsN elements ⋮ Optimal parallel algorithms for computing convex hulls and for sorting ⋮ The average performance of a parallel stable mariage algorithm ⋮ Hybridsort revisited and parallelized ⋮ All Nearest Smallers Made Simple ⋮ Fast and optimal simulations between CRCW PRAMs ⋮ On the performance of networks with multiple busses ⋮ Merging and sorting strings in parallel ⋮ An improved reliability bound of a probabilistic parallel integer sorting algorithm ⋮ A sublogarithmic convex hull algorithm ⋮ An optimal parallel algorithm for linear programming in the plane ⋮ Integer merging on EREW PRAM ⋮ A parallel computing framework for big data ⋮ Incomparability in parallel computation ⋮ Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm ⋮ Parallel computation and conflicts in memory access ⋮ An 0(log n) parallel algorithm for strong connectivity augmentation problem ⋮ Relating the power of the multiple associative computing (MASC) model to that of reconfigurable bus-based models ⋮ Processor-time tradeoffs in PRAM simulations ⋮ Expected parallel time and sequential space complexity of graph and digraph problems ⋮ Optimal parallel algorithms for point-set and polygon problems ⋮ Fast parallel string prefix-matching ⋮ Parallel rectilinear shortest paths with rectangular obstacles ⋮ Efficient dynamic range minimum query ⋮ Computing with Spikes: The Advantage of Fine-Grained Timing ⋮ Optimal parallel time bounds for the maximum clique problem on intervals ⋮ Tight complexity bounds for term matching problems ⋮ Parallel methods for visibility and shortest-path problems in simple polygons ⋮ A faster parallel algorithm for a matrix searching problem ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Randomized range-maxima in nearly-constant parallel time ⋮ A faster parallel algorithm for a matrix searching problem ⋮ Algorithms for some graph problems on a distributed computational model ⋮ Finding the upper envelope of n line segments in O(n log n) time ⋮ Optimal merging and sorting on the EREW PRAM ⋮ Constructing arrangements optimally in parallel ⋮ Parallel merging with restriction ⋮ Parallel iterated bucket sort ⋮ Parallel algorithms for merging and sorting ⋮ Resource bounds for parallel computation of threshold and symmetric functions ⋮ More general parallel tree contraction: Register allocation and broadcasting in a tree ⋮ Parallel construction and query of index data structures for pattern matching on square matrices ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS ⋮ A new parallel sorting algorithm based upon min-mid-max operations ⋮ A note on the parallel computation thesis ⋮ String distances and intrusion detection: Bridging the gap between formal languages and computer security ⋮ A parallel-design distributed-implementation (PDDI) general-purpose computer ⋮ An optimal parallel connectivity algorithm ⋮ How hard is computing the edit distance? ⋮ A theory of complexity for continuous time systems ⋮ Parallel algorithms for matrix polynomial division ⋮ On parallel integer sorting ⋮ Parallel comparison merging of many-ordered lists ⋮ Space-efficient parallel merging ⋮ Parallel comparison algorithms for approximation problems ⋮ Parallel solutions to geometric problems in the scan model of computation ⋮ ON THE POWER OF SOME PRAM MODELS ⋮ An optimal parallel algorithm for merging using multiselection
This page was built for publication: Finding the maximum, merging, and sorting in a parallel computation model
