Searching, Merging, and Sorting in Parallel Computation

DOI10.1109/TC.1983.1676138MaRDI QIDQ3038630zbMATH OpenFDO

Authors Clyde Kruskal

Publication date 1983

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/TC.1983.1676138

zbMATH Keywords

parallel computationsortingmergingsearchingcomparison problemsnumber of comparison steps

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Cited in

(33)

• Parallel algorithms for merging and sorting
• Polynomial terse sets
• Parallel priority queues
• Merging and sorting strings in parallel
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• Fast integer merging on the EREW PRAM
• Constructing arrangements optimally in parallel
• Fast integer merging on the EREW PRAM
• Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
• Improved parallel integer sorting without concurrent writing
• A nearly optimal deterministic parallel Voronoi diagram algorithm
• Heaps with bits
• A model of sequential computation with Pipelined access to memory
• Sorting strings and constructing digital search trees in parallel
• Parallel comparison algorithms for approximation problems
• Sweep methods for parallel computational geometry
• A complexity theory of efficient parallel algorithms
• Parallel selection
• Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm
• Routing, merging, and sorting on parallel models of computation
• Parallel merging with restriction
• Parallel construction of a suffix tree with applications
• Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs
• An efficient parallel algorithm for finding minimum weight matching for points on a convex polygon
• Sorting in linear time?
• Space-efficient parallel merging
• Integer merging on EREW PRAM
• Line-segment intersection reporting in parallel
• Parallel computation of the Burrows Wheeler transform in compact space
• Fast sequential and parallel algorithms for finding extremal sets
• Finding a minimum-weight k-link path in graphs with the concave Monge property and applications
• Parallel comparison merging of many-ordered lists
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

This page was built for publication: Searching, Merging, and Sorting in Parallel Computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3038630)