## Abstract

Randomized selection algorithms on k-dimensional mesh-connected computers with multiple broadcasting are proposed in this paper. We first show that a leader can be elected in O(log N) time on any k-dimensional mesh-connected computers with multiple broadcasting of size N. We then show that we can find the p-th smallest element among a data set of size N in O((log N + k + N^{1/(k(k+1))}) log N) expected time using a regular N^{1/k} × ... × N^{1/k} k-dimensional mesh and in O((log N + k^{2}N^{1/(k2k)}) log N) expected time using an irregular N^{(2k-1 k+1)/{k2k}} × N(2k-2 k+1)/^{(k2k)} × ... × N^{(k+1)/(k2k)} k-dimensional mesh. This leads to a selection algorithm which runs in O((log,N)^{2}) expected time on a regular ((log N/log log N)^{1/2})-dimensional mesh or on an irregular (log log N)-dimensional mesh each with N processors. To our best knowledge, this is the first polylogarithmic selection algorithm on meshes with multiple broadcasting.

Original language | English (US) |
---|---|

Pages (from-to) | x5-144 |

Journal | Computer Journal |

Volume | 39 |

Issue number | 2 |

DOIs | |

State | Published - 1996 |

Externally published | Yes |

## ASJC Scopus subject areas

- Computer Science(all)