𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Probabilistic Networks for Selection, Merging, and Sorting

✍ Scribed by T. Leighton; Y. Ma; T. Suel

Publisher
Springer
Year
1997
Tongue
English
Weight
220 KB
Volume
30
Category
Article
ISSN
1433-0490

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Parallel Sorting Algorithm Using Multiwa
Parallel Sorting Algorithm Using Multiway Merge and Its Implementation on a Multi-Mesh Network
✍ Bhabani P. Sinha; Amar Mukherjee πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 288 KB

In this paper, we present a parallel sorting algorithm using the technique of multi-way merge. This algorithm, when implemented on a t dimensional mesh having n t nodes (t>2), sorts n t elements in O((t 2 &3t+2) n) time, thus offering a better order of time complexity than the [((t 2 &t) n log n)Γ‚2+

Perfectly overlapped merging and sorting
Perfectly overlapped merging and sorting on a two-way linear array
✍ Yen-Chun Lin πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 475 KB

We present a perfectly overlapped merging algorithm, which can require almost only input time to perform merge sorting on a linear array of processors. The optimal merge order that minimizes the merge sorting time is obtained in constant time. The merging algorithm and a previously proposed runs-gen

Selection, Routing, and Sorting on the S
Selection, Routing, and Sorting on the Star Graph
✍ Sanguthevar Rajasekaran; David S.L. Wei πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 270 KB

We consider the problems of selection, routing, and sorting on an n-star graph (with n! nodes), an interconnection network which has been proven to possess many special properties. We identify a tree like subgraph (which we call a "(k, 1, k) chain network") of the star graph which enables us to desi