A Selection Algorithm for X + Y on Mesh
Tarun Anand, Phalguni Gupta · Parallel Processing Letters · 1998
This paper presents a selection algorithm for finding the k-th largest element in the cartesian sum of two sets X and Y, each of size n, on a mesh connected model. The algorithm has a time complexity of [Formula: see text], using P processors, where P < n2. The algorithm is adaptive but [Formula: see text] away from cost optimality.