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 条
  • [31] TRUSTED NETWORKS.
    Farr, Tom
    Computer Bulletin (London), 1988, (pt 2): : 25 - 27
  • [32] INSERTION NETWORKS.
    Davio, M.
    Ronse, C.
    IEEE Transactions on Computers, 1985, C-34 (06) : 565 - 570
  • [33] R networks.
    Tzitzeica
    COMPTES RENDUS HEBDOMADAIRES DES SEANCES DE L ACADEMIE DES SCIENCES, 1911, 153 : 1127 - 1129
  • [34] SIGNALLING NETWORKS.
    Hemrin, Per
    Rassmuson, Goran
    Tele English ed., 1981, 33 (02): : 16 - 23
  • [35] Optimal Location and Size for Various Renewable Distributed Generators in Distribution Networks.
    Castillo, Tuesman D.
    Saad, Maarouf
    2017 IEEE PES INNOVATIVE SMART GRID TECHNOLOGIES CONFERENCE - LATIN AMERICA (ISGT LATIN AMERICA), 2017,
  • [36] COMPUTER NETWORKS.
    Buczkowska, T.
    Journal of Electrical and Electronics Engineering, Australia, 1986, 6 (04): : 259 - 269
  • [37] Desperate networks.
    Beard, RM
    LIBRARY JOURNAL, 2006, 131 (08) : 96 - 96
  • [38] DECISION NETWORKS.
    Clark, Jennifer A.
    Hastings, N.A.J.
    1600, (28):
  • [39] Interactome networks.
    Vidal, M
    DEVELOPMENTAL BIOLOGY, 2005, 283 (02) : 579 - 579
  • [40] CALCULATION OF NETWORKS.
    Nelles, Dieter
    1600,
12345