
Accession Number : ADA114857
Title : A Logarithmic Time Sort for Linear Size Networks.
Descriptive Note : Technical rept.,
Corporate Author : HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB
Personal Author(s) : Reif,John H ; Valiant,Leslie G
PDF Url : ADA114857
Report Date : May 1982
Pagination or Media Count : 28
Abstract : We give a probabilistic algorithm for sorting on constant valence networks of N nodes such as the cubeconnected cycles. We prove that for any input set of 0(N) keys, the algorithm's execution time is greater than a constant times log N with vanishingly low likelihood. Since this constant factor is small our parallel sorting algorithm may be practical to implement. (Author)
Descriptors : *Algorithms, *Network flows, Probability, Problem solving, Sorting, Routing, Sequential analysis, Computations
Subject Categories : Statistics and Probability
Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE