A logarithmic time sort for linear size networks
Publication
, Journal Article
Reif, JH; Valiant, LG
Published in: Journal of the ACM (JACM)
January 1, 1987
A randomized algorithm that sorts on an N node network with constant valence in O(log N) time is given. More particularly, the algorithm sorts N items on an N-node cube-connected cycles graph, and, for some constant k, for all large enough α, it terminates within kα log N time with probability at least 1 - N-α. © 1987, ACM. All rights reserved.
Duke Scholars
Altmetric Attention Stats
Dimensions Citation Stats
Published In
Journal of the ACM (JACM)
DOI
EISSN
1557-735X
ISSN
0004-5411
Publication Date
January 1, 1987
Volume
34
Issue
1
Start / End Page
60 / 76
Related Subject Headings
- Computation Theory & Mathematics
- 46 Information and computing sciences
- 08 Information and Computing Sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Valiant, L. G. (1987). A logarithmic time sort for linear size networks. Journal of the ACM (JACM), 34(1), 60–76. https://doi.org/10.1145/7531.7532
Reif, J. H., and L. G. Valiant. “A logarithmic time sort for linear size networks.” Journal of the ACM (JACM) 34, no. 1 (January 1, 1987): 60–76. https://doi.org/10.1145/7531.7532.
Reif JH, Valiant LG. A logarithmic time sort for linear size networks. Journal of the ACM (JACM). 1987 Jan 1;34(1):60–76.
Reif, J. H., and L. G. Valiant. “A logarithmic time sort for linear size networks.” Journal of the ACM (JACM), vol. 34, no. 1, Jan. 1987, pp. 60–76. Scopus, doi:10.1145/7531.7532.
Reif JH, Valiant LG. A logarithmic time sort for linear size networks. Journal of the ACM (JACM). 1987 Jan 1;34(1):60–76.
Published In
Journal of the ACM (JACM)
DOI
EISSN
1557-735X
ISSN
0004-5411
Publication Date
January 1, 1987
Volume
34
Issue
1
Start / End Page
60 / 76
Related Subject Headings
- Computation Theory & Mathematics
- 46 Information and computing sciences
- 08 Information and Computing Sciences