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 条
  • [41] Neural networks.
    Hancock, P
    BRITISH JOURNAL OF MATHEMATICAL & STATISTICAL PSYCHOLOGY, 1999, 52 : 321 - 322
  • [42] Protoplasmic networks.
    Bernard, HM
    NATURE, 1902, 65 : 534 - 535
  • [43] DATA NETWORKS.
    Dempf, Gerhard
    Grenzdoerfer, Sven
    AEG-Telefunken Progress (Allgemeine Elektricitaets-Gesellschaft), 1981, (1-2): : 24 - 26
  • [44] Computer Networks.
    Schwarz da Silva, J.A.
    Guindon, Rene
    1600, (58):
  • [45] Computer Networks.
    Catier, Eric
    Electronique industrielle, 1982, (39): : 55 - 63
  • [46] EIGENVALUE PROBLEM FOR LINEAR 2nx2-TERMINAL NETWORKS.
    Onishchuk, A.G.
    1978, 23 (06): : 56 - 59
  • [47] Geometry of river networks. II. Distributions of component size and number
    Dodds, PS
    Rothman, DH
    PHYSICAL REVIEW E, 2001, 63 (01):
  • [48] LINEAR PROBING SORT
    DOBOSIEWICZ, W
    COMPUTER JOURNAL, 1991, 34 (04): : 370 - 373
  • [49] NON-LINEAR PROGRAMMING TECHNIQUE FOR ANALYSIS OF MINE VENTILATION NETWORKS.
    Bhamidipati, S.
    Procarione, J.A.
    Transactions of the Institution of Mining and Metallurgy, Section A: Mining Technology, 1986, 95 : 8 - 14
  • [50] Logarithmic-time updates and queries in probabilistic networks
    Delcher, AL
    Grove, AJ
    Kasif, S
    Pearl, J
    JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 1996, 4 : 37 - 59
12345