LOGARITHMIC TIME SORT FOR LINEAR SIZE NETWORKS.

被引：0
|
作者：
Reif, John H. [1 ]
Valiant, Leslie G. [1 ]
机构：
[1] Harvard Univ, Cambridge, MA, USA, Harvard Univ, Cambridge, MA, USA
来源：
| 1600年 / 34期
关键词：
COMPUTER PROGRAMMING - Algorithms;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A randomized parallel 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 alpha , it terminates with k alpha log N time with probability at least 1 minus N** minus ** alpha .
引用
收藏
相关论文
共 50 条
  • [1] A LOGARITHMIC TIME SORT FOR LINEAR SIZE NETWORKS
    REIF, JH
    VALIANT, LG
    JOURNAL OF THE ACM, 1987, 34 (01) : 60 - 76
  • [2] ON A TIME DOMAIN SYNTHESIS METHOD FOR LINEAR NETWORKS.
    Kojima, Norio
    Machida, Toichi
    Shinozaki, Toshio
    Proceedings - IEEE International Symposium on Circuits and Systems, 1979, : 298 - 301
  • [3] Assessing the size of motion trajectory networks.
    Watamaniuk, SNJ
    INVESTIGATIVE OPHTHALMOLOGY & VISUAL SCIENCE, 2001, 42 (04) : S737 - S737
  • [4] Methods for Tolerance Optimization of Linear Networks.
    Schwarz, Peter
    1600, (07):
  • [5] Determination of Source Resistances in Linear Electronic Networks.
    Albrecht, H.
    Nachrichtentechnik Elektronik, 1974, 24 (07): : 257 - 258
  • [6] Multiple objective linear programming for metabolic networks.
    Sun, M
    Xiong, MM
    AMERICAN JOURNAL OF HUMAN GENETICS, 2003, 73 (05) : 420 - 420
  • [7] INVARIANT PRODUCT AND RATIO THEOREMS FOR LINEAR NETWORKS.
    Basu, D.
    Journal of the Institution of Engineers (India): Electrical Engineering Division, 1986, 66 (pt 3-4): : 127 - 129
  • [8] AMPLITUDE SCALING OF ARBITRARY LINEAR DIGITAL NETWORKS.
    Kwan, Hon Keung
    IEEE Transactions on Acoustics, Speech, and Signal Processing, 1984, ASSP-32 (06): : 1240 - 1242
  • [9] ROUNDOFF NOISE OF ARBITRARY LINEAR DIGITAL NETWORKS.
    Kwan, Hon Keung
    Constantinides, A.G.
    1600, (ASSP-33):
  • [10] Computing the Inverse Sort Transform in Linear Time
    Nong, Ge
    Zhang, Sen
    Chan, Wai Hong
    ACM TRANSACTIONS ON ALGORITHMS, 2011, 7 (02)
12345