Tight Bounds on the Complexity of Parallel Sorting
From MaRDI portal
Publication:3219774
DOI10.1109/TC.1985.5009385zbMath0556.68024OpenAlexW2137239103MaRDI QIDQ3219774
Publication date: 1985
Published in: IEEE Transactions on Computers (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/tc.1985.5009385
parallel computationVLSIcircuit complexityparallel sortingcommunication complexitypacket routingarea-time tradeoffsbounded-degree fixed-connection network
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Theory of operating systems (68N25)
Related Items
Methods for message routing in parallel machines, Algorithms for parallel memory, I: Two-level memories, Parallel integer sorting using small operations, Towards a better understanding of pure packet routing, An optimal speed-up parallel algorithm for triangulating simplicial point sets in space, Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults, Sorting in constant number of row and column phases on a mesh, MODELS AND RESOURCE METRICS FOR PARALLEL AND DISTRIBUTED COMPUTATION∗, SORTING AND SELECTION ON DISTRIBUTED MEMORY BUS COMPUTERS, A unified \(O(\log N)\) and optimal sorting vector algorithm, Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs, Sloping-and-shaking, Time lower bounds for parallel sorting on a mesh-connected processor array, An efficient parallel algorithm for random sampling, A randomized sorting algorithm on the BSP model, Real-time emulations of bounded-degree networks, Beyond the worst-case bisection bound: Fast sorting and ranking on meshes, Faster deterministic sorting through better sampling., Representing shared data on distributed-memory parallel computers, A note on the token distribution problem, On the theory of interconnection networks for parallel computers, The complexity of deterministic PRAM simulation on distributed memory machines, Constructing sorting networks from k-sorters, More Efficient Parallel Integer Sorting, Counting clique trees and computing perfect elimination schemes in parallel, An efficient multiway merging algorithm, Periodic comparator networks, Deterministic sorting in nearly logarithmic time on the hypercube and related computers, Improved upper bounds on Shellsort
