article · SIAM Journal on Computing · 1981
Parallel Sorting with Constant Time for Comparisons
Cited by 44Abstract and details only
Abstract
We prove that there exist graphs with n vertices and at most $2n^{5/3} \log n$ edges for which every acyclic orientation has in its transitive closure at least $\begin{pmatrix} n \\ 2 \end{pmatrix} - 10n^{5/3} $ arcs. We conclude that with $2n^{5/3} \log n$ parallel processors n items may be sorted with all comparisons arranged in two time intervals. We also show that $\frac{1}{9}n^{3/2} $ processors are not sufficient to achieve the same end. These results are extended to parallel sorting in k time intervals, and related to other work on parallel sorting. The existence of sorting algorithms achieving the bounds is proved by nonconstructive methods. (The constants quoted in the abstract are somewhat improved in the paper.)
Cite this paper
Häggkvist, R., & Hell, P. (1981). Parallel Sorting with Constant Time for Comparisons. SIAM Journal on Computing, 10(3), 465–472. https://doi.org/10.1137/0210034
Häggkvist, Roland, and Pavol Hell. “Parallel Sorting with Constant Time for Comparisons.” SIAM Journal on Computing, vol. 10, no. 3, 1981, pp. 465–72, https://doi.org/10.1137/0210034.
Häggkvist, Roland, and Pavol Hell. 1981. “Parallel Sorting with Constant Time for Comparisons.” SIAM Journal on Computing 10 (3): 465–72. https://doi.org/10.1137/0210034.
Häggkvist, R. and Hell, P. (1981) ‘Parallel Sorting with Constant Time for Comparisons’, SIAM Journal on Computing, 10(3), pp. 465–472. Available at: https://doi.org/10.1137/0210034.
@article{haggkvist1981parallel,
title = {{Parallel Sorting with Constant Time for Comparisons}},
author = {Häggkvist, Roland and Hell, Pavol},
journal = {SIAM Journal on Computing},
volume = {10},
number = {3},
pages = {465--472},
year = {1981},
doi = {10.1137/0210034}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.