{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T19:41:00Z","timestamp":1776714060341,"version":"3.51.2"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1991,4,1]],"date-time":"1991-04-01T00:00:00Z","timestamp":670464000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[1991,4]]},"DOI":"10.1007\/bf01407839","type":"journal-article","created":{"date-parts":[[2005,4,3]],"date-time":"2005-04-03T03:56:05Z","timestamp":1112500565000},"page":"95-131","source":"Crossref","is-referenced-by-count":7,"title":["Efficient algorithms for parallel sorting on mesh multicomputers"],"prefix":"10.1007","volume":"20","author":[{"given":"V.","family":"Singh","sequence":"first","affiliation":[]},{"given":"V.","family":"Kumar","sequence":"additional","affiliation":[]},{"given":"G.","family":"Agha","sequence":"additional","affiliation":[]},{"given":"C.","family":"Tomlinson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"7","key":"CR1","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1109\/TC.1985.1676603","volume":"34","author":"Hans-Werner Lang","year":"1985","unstructured":"Hans-Werner Lang, Manfred Schimmler, Hartmut Schmeck, and Heiko Schroder, Systolic Sorting on a Mesh-Connected Network,IEEE Transactions on Computers C-34(7):652?658 (July 1985).","journal-title":"IEEE Transactions on Computers C"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr and A. Shamir, An Optimal Sorting Algorithm for Mesh-Connected Computers,Proceedings STOC, pp. 255?263 (1986).","DOI":"10.1145\/12130.12156"},{"issue":"6","key":"CR3","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/BF01389001","volume":"16","author":"Vipin Kumar","year":"1987","unstructured":"Vipin Kumar and V. Nageshwara Rao Parallel Depth-First Search, Part II: Analysis,International Journal of Parallel Programming 16(6):501?519 (1987).","journal-title":"International Journal of Parallel Programming"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"Manfred Kunde, Routing and Sorting on Mesh-Connected Arrays,Proceedings of the AWOC Conference, pp. 423?433 (1988). Also available asSpringer LNCS, Vol. 319.","DOI":"10.1007\/BFb0040409"},{"key":"CR5","unstructured":"S. G. Akl.The Design and Analysis of Parallel Algorithms, Prentice-Hall, p. 44 (1989)."},{"key":"CR6","unstructured":"Bogdan S. Chlebus and Imrich Vrto, Parallel Quicksort,Journal of Parallel and Distributed Processing (to appear)."},{"key":"CR7","unstructured":"Anshul Gupta and Vipin Kumar, On the Scalability of FFT on Parallel Computers,Proceedings of the Frontiers 90 Conference on Massively Parallel Computation (October 1990). An extended version of the paper is available as a Technical Report from the Department of Computer Science, and as TR 90-20 from Army High Performance Computing Research Center, University of Minnesota, Minneapolis."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"Vipin Kumar and Vineet Singh, Scalability of Parallel Algorithms for the All-Pairs Shortest Path Problem,Journal of Parallel and Distributed Processing (special issue on massively parallel computation) (October 1991). A short version appears in theProc. of the Int'l. Conf. on Parallel Processing (1990).","DOI":"10.1016\/0743-7315(91)90083-L"},{"key":"CR9","unstructured":"Vipin Kumar and V. Nageshwara Rao, Load Balancing on the Hypercube Architecture,Proceedings of the Conference on Hypercubes, Concurrent Computers and Applications, pp. 603?608 (1989)."},{"key":"CR10","volume-title":"Hypercube Algorithms for Image Processing and Pattern Recognition","author":"S. Ranka","year":"1990","unstructured":"S. Ranka and S. Sahni,Hypercube Algorithms for Image Processing and Pattern Recognition, Springer-Verlag, New York 1990."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TC.1979.1675216","volume":"28","author":"D. Nassimi","year":"1979","unstructured":"D. Nassimi and S. Sahni, Bitonic Sort on a Mesh-Connected Parallel ComputerIEEE Transactions on Computers C-28:2?7 (1979).","journal-title":"IEEE Transactions on Computers C"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1145\/359461.359481","volume":"21","author":"C. Thompson","year":"1977","unstructured":"C. Thompson and H. T. Kung, Sorting on a Mesh-Connected Parallel Computer,Communications of the ACM 21:263?271 (1977).","journal-title":"Communications of the ACM"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"William J. Dally,A VLSI Architecture for Concurrent Data Structures. PhD Thesis, California Institute of Technology (March 1986).","DOI":"10.1007\/978-1-4613-1995-5_5"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"J. Lee, E. Shragowitz, and S. Sahni, A Hypercube Algorithm for the 0\/1 Knapsack Problem,Proceedings of International Conference on Parallel Processing, pp. 699?706 (1987).","DOI":"10.1016\/0743-7315(88)90007-X"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"M. A. Huang, Solving Some Graph Problems with Optimal or Near Optimal Speedup on Mesh-of-Trees Networks,Proceedings of 26th Annual IEEE Symposium on Foundations of Computer Science, pp. 232?240 (1985).","DOI":"10.1109\/SFCS.1985.52"},{"key":"CR16","unstructured":"J. Jenq and S. Sahni, All Pairs Shortest Paths on a Hypercube Multiprocessor,International Conference on Parallel Processing, pp. 713?716 (1987)."},{"key":"CR17","volume-title":"Designing Efficient Algorithms for Parallel Computers","author":"Michael J. Quinn","year":"1987","unstructured":"Michael J. Quinn,Designing Efficient Algorithms for Parallel Computers, McGraw Hill, New York (1987)."},{"key":"CR18","unstructured":"R. Halstead, Multilisp: A Language for Concurrent Symbolic Computation,ACM Trans. on Prog. Languages and Systems, pp. 501?538 (1985)."},{"issue":"6","key":"CR19","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1109\/MC.1985.1662925","volume":"18","author":"K. Murakami","year":"1985","unstructured":"K. Murakami, T. Kakuta, R. Onai, and N. Ito, Research on Parallel Machine Architecture for Fifth-Generation Computer Systems,IEEE Computer 18(6):76?92 (1985).","journal-title":"IEEE Computer"},{"issue":"1","key":"CR20","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1109\/12.46289","volume":"39","author":"P. Heidelberger","year":"1990","unstructured":"P. Heidelberger, A. Norton, and J. T. Robinson, Parallel Quicksort Using Fetch-and-Add.,IEEE Transactions on Computers 39(1):133?138 (1990).","journal-title":"IEEE Transactions on Computers"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1145\/5925.5930","volume":"33","author":"L. Devroye","year":"1986","unstructured":"L. Devroye, A Note on the Height of Binary Search Trees,Journal of Association of Computing Machinery 33:489?498 (1986).","journal-title":"Journal of Association of Computing Machinery"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1109\/TC.1978.1674957","volume":"27","author":"G. Baudet","year":"1978","unstructured":"G. Baudet and D. Stevenson, Optimal Sorting Algorthms for Parallel ComputersIEEE Transactions on Computers C-27:84?87 (1978).","journal-title":"IEEE Transactions on Computers C"},{"issue":"18","key":"CR23","first-page":"329","volume":"1","author":"G. Fox","year":"1988","unstructured":"G. Fox et al.,Solving Problems on Concurrent Computers, Prentice-Hall1(18):329?333 (1988).","journal-title":"Solving Problems on Concurrent Computers"},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"Vipin Kumar and Anshul Gupta, Analyzing Scalability of Parallel Algorthms and Architectures, Technical Report TR-91-18, Computer Science Department, University of Minnesota (June 1991). A short version of the paper appears in the Proceedings of the 1991 International Conference on Supercomputing, Germany.","DOI":"10.1145\/109025.109118"},{"issue":"5","key":"CR25","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1145\/42411.42415","volume":"31","author":"John L. Gustafson","year":"1988","unstructured":"John L. Gustafson, Reevaluating Amdahl's Law,Communications of the ACM 31(5):532?533 (1988).","journal-title":"Communications of the ACM"},{"issue":"4","key":"CR26","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1137\/0909041","volume":"9","author":"John L. Gustafson","year":"1988","unstructured":"John L. Gustafson, Gary R. Montry, and Robert E. Benner, Development of Parallel Methods for a 1024-Processor Hypercube,SIAM Journal on Scientific and Statistical Computing 9(4):609?638 (1988).","journal-title":"SIAM Journal on Scientific and Statistical Computing"},{"key":"CR27","series-title":"Technical Report RC13572","volume-title":"A Complexity Theory of Efficient Parallel Algorithms","author":"Clyde P. Kruskal","year":"1988","unstructured":"Clyde P. Kruskal, Larry, Rudolph, and Marc Snir, A Complexity Theory of Efficient Parallel Algorithms, Technical Report RC13572, IBM TJ-Watson Research Center, New York (1988)."},{"issue":"12","key":"CR28","doi-asserted-by":"crossref","first-page":"1170","DOI":"10.1145\/7902.7903","volume":"29","author":"D. Hillis","year":"1986","unstructured":"D. Hillis and G. L. Steele, Data Parallel Algorithms,Communications of the ACM 29(12):1170?1183 (1986).","journal-title":"Communications of the ACM"},{"key":"CR29","unstructured":"Bill Athas, Fine Grain Concurrent Computations, PhD Thesis, Computer Science Department, California Institute of Technology (1987). Also published as Technical Report 5442:TR:87."},{"key":"CR30","volume-title":"Parallel Program Design: A Foundation","author":"K. M. Chandy","year":"1988","unstructured":"K. M. Chandy and J. Misra,Parallel Program Design: A Foundation, Addison-Wesley, Reading, Massachusetts (1988)."},{"key":"CR31","unstructured":"E. Shapiro (ed.)Concurrent Prolog 1(7):207?242. MIT Press (1987)."},{"key":"CR32","first-page":"99","volume":"XXVIII","author":"Stephen A. Cook","year":"1981","unstructured":"Stephen A. Cook, Towards a Complexity Theory of Synchronous Parallel Computation,L'Enseignement Math\u00e9matique XXVIII:99?124 (1981).","journal-title":"L'Enseignement Math\u00e9matique"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01407839.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01407839\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01407839","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T17:03:02Z","timestamp":1586192582000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01407839"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,4]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,4]]}},"alternative-id":["BF01407839"],"URL":"https:\/\/doi.org\/10.1007\/bf01407839","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,4]]}}}