Parallel permutation and sorting algorithms and a new generalized connection network
From MaRDI portal
Publication:3949979
DOI10.1145/322326.322329zbMath0488.68045MaRDI QIDQ3949979
Sartaj K. Sahni, David Nassimi
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
parallel processors; interconnection architectures; perfect shuffle computer; cube computer; generalized connection network; single-instruction- stream multiple-data-stream architectures
68P10: Searching and sorting
94C99: Circuits, networks
68N25: Theory of operating systems
68N99: Theory of software
Related Items
TIME-OPTIMAL GEOMETRIC ALGORITHMS IN HYPERCUBIC NETWORKS, Optimal parallel algorithms for computing convex hulls and for sorting, A new parallel sorting algorithm based upon min-mid-max operations, An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem, An optimal time bound for oblivious routing, On some connections between permutations and coding, An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits, 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, Deterministic sorting in nearly logarithmic time on the hypercube and related computers, Divide-and-conquer algorithms on the hypercube, A local-sparing design methodology for fault-tolerant multiprocessors, Architecture independent parallel selection with applications to parallel priority queues, Some Graph-Colouring Theorems with Applications to Generalized Connection Networks, A parallel sorting scheme whose basic operation sortsN elements, A Parallel Algorithm for Cost-Optimal Generation of Permutations ofrout ofnItems, Efficient enumeration of cyclic permutations in situ