Parallel permutation and sorting algorithms and a new generalized connection network

DOI10.1145/322326.322329zbMath0488.68045OpenAlexW2047528205MaRDI QIDQ3949979

David Nassimi, Sartaj K. Sahni

Publication date: 1982

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322326.322329

zbMATH Keywords

parallel processorsinterconnection architecturesperfect shuffle computercube computergeneralized connection networksingle-instruction- stream multiple-data-stream architectures

Mathematics Subject Classification ID

Searching and sorting (68P10) Circuits, networks (94C99) Theory of operating systems (68N25) Theory of software (68N99)

Related Items (19)

Direct bulk-synchronous parallel algorithms ⋮ An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem ⋮ An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits ⋮ TIME-OPTIMAL GEOMETRIC ALGORITHMS IN HYPERCUBIC NETWORKS ⋮ Divide-and-conquer algorithms on the hypercube ⋮ A parallel sorting scheme whose basic operation sortsN elements ⋮ Optimal parallel algorithms for computing convex hulls and for sorting ⋮ A randomized sorting algorithm on the BSP model ⋮ A local-sparing design methodology for fault-tolerant multiprocessors ⋮ Architecture independent parallel selection with applications to parallel priority queues ⋮ An optimal time bound for oblivious routing ⋮ A Parallel Algorithm for Cost-Optimal Generation of Permutations ofrout ofnItems ⋮ Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers ⋮ Data reduction and fast routing: A strategy for efficient algorithms for message-passing parallel computers ⋮ Efficient enumeration of cyclic permutations in situ ⋮ A new parallel sorting algorithm based upon min-mid-max operations ⋮ On some connections between permutations and coding ⋮ Deterministic sorting in nearly logarithmic time on the hypercube and related computers ⋮ Some Graph-Colouring Theorems with Applications to Generalized Connection Networks

This page was built for publication: Parallel permutation and sorting algorithms and a new generalized connection network