Parallel Sorting with Constant Time for Comparisons

DOI10.1137/0210034zbMath0461.68062OpenAlexW2015188932MaRDI QIDQ3911406

Pavol Hell, Roland Haeggkvist

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 algorithmacyclic orientationtransitive closure

Mathematics Subject Classification ID

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

Related Items (16)

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

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