Mesh sorting and selection optimal on the average

被引：0
|
作者：
Chlebus, BS
机构：
来源：
COMPUTERS AND ARTIFICIAL INTELLIGENCE | 1997年 / 16卷 / 02期
关键词：
parallel algorithm; mesh-connected computer; average performance; optimal algorithm; sorting; selection;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
We consider 1-1 sorting and selection problems on an n x n mesh-connected processor arrays. Algorithms are developed which are fast with respect to the average-time performance. We show that selection can be accomplished in the average time n + o(n), and sorting in the average time 2.n + o(n). Matching lower bounds are also proved.
引用
收藏
页码：141 / 152
页数：12
相关论文
共 50 条
  • [41] Optimal parallel selection
    Han, YJ
    PROCEEDINGS OF THE FOURTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2003, : 1 - 9
  • [42] Optimal Parallel Selection
    Han, Yijie
    ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (04)
  • [43] Sorting-based selection algorithms for hypercubic networks
    Berthomé, P
    Ferreira, A
    Maggs, BM
    Perennes, S
    Plaxton, CG
    ALGORITHMICA, 2000, 26 (02) : 237 - 254
  • [44] Optimal sorting method and application to SSRF booster dipoles
    Zhang Man-Zhou
    Hou Jie
    Li Hao-Hu
    Liu Gui-Min
    Li De-Ming
    CHINESE PHYSICS C, 2008, 32 (11) : 924 - 927
  • [45] Optimal sorting method and application to SSRF booster dipoles
    张满洲
    后接
    李浩虎
    刘桂民
    李德明
    中国物理C, 2008, (11) : 924 - 927
  • [46] Optimal conditional estimation: Average case setting
    Kacewicz, B
    JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2001, 109 (03) : 649 - 666
  • [47] Optimal Conditional Estimation: Average Case Setting
    B. Kacewicz
    Journal of Optimization Theory and Applications, 2001, 109 : 649 - 666
  • [48] Optimal deterministic sorting and routing on grids and tori with diagonals
    Kunde, M
    Niedermeier, R
    Reinhardt, K
    Rossmanith, P
    ALGORITHMICA, 1999, 25 (04) : 438 - 458
  • [49] Optimal sorting of raw materials for use in different products
    Berget, I
    Aamodt, A
    Færgestad, EM
    Næs, T
    CHEMOMETRICS AND INTELLIGENT LABORATORY SYSTEMS, 2003, 67 (02) : 79 - 93
  • [50] Sorting, selection, and routing on the array with reconfigurable optical buses
    Rajasekaran, S
    Sahni, S
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1997, 8 (11) : 1123 - 1132
12345