A parallel selection algorithm |
| |
Authors: | P. Gupta G. P. Bhattacharjee |
| |
Affiliation: | (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 {xi+yj|xi X andyj Y i,j} whereX=(x1,x2, ..,xn) andY=(y1,y2, ...,yn) 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(n1+1/ ) processors is presented where is a pre-assigned constant lying between 1 and 2. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|