A parallel selection algorithm |
| |
| Authors: | P Gupta G P Bhattacharjee |
| |
| Institution: | (1) Department of Mathematics, Indian Institute of Technology, 721 302 Kharagpur, India;(2) Present address: IPAD/RSA, Space Applications Centre, 380 053 Ahmedabad, India |
| |
| Abstract: | The problem of selecting thekth largest or smallest element of {x
i
+y
j
|x
i
 X andy
j
Y  i,j} whereX=(x
1,x
2, ..,x
n
) andY=(y
1,y
2, ...,y
n
) are two arrays ofn elements each, is considered. Certain improvements to an existing algorithm are proposed. An algorithm requiringO(logk·logn) units of time on a Shared Memory Model of a parallel computer havingO(n
1+1/ ) processors is presented where is a pre-assigned constant lying between 1 and 2. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
