Parallel Sorting with Constant Time for Comparisons

DOI10.1137/0210034MaRDI QIDQ3911406zbMATH OpenOpenAlexFDO

Authors Roland Häggkvist, Pavol Hell

Publication date 1981

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0210034

zbMATH Keywords

parallel algorithmtransitive closureacyclic orientation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10)

Cited in

(16)

• A parallel sorting scheme whose basic operation sortsN elements
• Sorting and Merging in Rounds
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Constant time parallel sorting: An empirical view.
• Sorting in rounds
• On partial sorting in restricted rounds
• Graphs whose every transitive orientation contains almost every relation
• Parallel comparison algorithms for approximation problems
• Routing, merging, and sorting on parallel models of computation
• Sorting in one round
• Finding an unknown acyclic orientation of a given graph
• Parallel sorting
• Dense expanders and pseudo-random bipartite graphs
• Search problems: One, two or many rounds
• A new parallel sorting algorithm based upon min-mid-max operations
• Parallel comparison merging of many-ordered lists

This page was built for publication: Parallel Sorting with Constant Time for Comparisons

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