pdbain@wateng.UUCP (Peter Bain) (05/15/85)
%A Howard B. Demuth
%T Electronic Data Sorting
%J IEEE Transactions on Computers
%I IEEE
%V C-34
%N 4
%D Apr. 1985
%P 296-308
%X work was originally published in 1956 - contains a number of anachronisms,
but valuable theoretical results
%K complexity theory information theory optimal parallel sorting
information gathering
%A Eric Dittert
%A Michael J. O'Donnell
%T Lower Bounds for Sorting with Realistic Instruction Sets
%J IEEE Transactions on Computers
%I IEEE
%V C-34
%N 4
%D Apr. 1985
%P 311-317
%K decision tree division interpolation lower bounds ram random access
machine rational functions sorting
%A Heikki Mannila
%T Measures of Presortedness and Optimal Sorting Algorithms
%J IEEE Transactions on Computers
%I IEEE
%V C-34
%N 4
%D Apr. 1985
%P 318-325
%K sortedness local insertion sort measures optimality inversions
longest ascending subsequnce
%A Larry Rudolph
%T A Robust Sorting Network
%J IEEE Transactions on Computers
%I IEEE
%V C-34
%N 4
%D Apr. 1985
%P 326-335
%K fault-tolerant computing parallel processing recirculating networks
shuffle-exchange sorting networks vlsi
%A Gianfranco Bilardi
%A Franco P. Preparata
%T A Minimum Area VLSI Network for O(log n) Time Sorting
%J IEEE Transactions on Computers
%I IEEE
%V C-34
%N 4
%D Apr. 1985
%P 336-343
%K area-time tradeoff bitonic merging combination sorting cube
connected cycles mesh optimal algorithms orthogonal trees parallel
computation
%A Tom Leighton
%T Tight Bounds on the Complexity of Parallel Sorting
%J IEEE Transactions on Computers
%I IEEE
%V C-34
%N 4
%D Apr. 1985
%P 344-354
%K arae-time tradeoff circuit complexity communication fixed
connection network packet routing parallel computation vlsi
%A Alan R. Siegel
%T Minimum Storage Sorting Networks
%J IEEE Transactions on Computers
%I IEEE
%V C-34
%N 4
%D Apr. 1985
%P 355-361
%K data compression lower bounds minimum storgae digital sorters
noncompression sorting network vlsi complexity
--
- peter bain
...!{allegra|decvax|clyde|ihnp4 }!watmath!wateng!pdbain
hard mail: CCNG, CPH-2369A, University of Waterloo,
Waterloo, Ont. Canada N2M 5G4
telephone: (519) 885-1211 x2810