{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:37:14Z","timestamp":1725457034158},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540541516"},{"type":"electronic","value":"9783540474715"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/bfb0035093","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T06:20:09Z","timestamp":1134282009000},"page":"6-24","source":"Crossref","is-referenced-by-count":5,"title":["Towards a single model of efficient computation in real parallel machines"],"prefix":"10.1007","author":[{"given":"Pilar","family":"de la Torre","sequence":"first","affiliation":[]},{"given":"Clyde P.","family":"Kruskal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,23]]},"reference":[{"key":"2_CR1","unstructured":"A. Aggarwal, A. Chandra, and M. Snir. Communication complexity of prams. Technical Report RC 14998(64644), IBM Tech. Report, 1989."},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, A. Chandra, and M. Snir. On communication latency of prams. Technical Report RC 14973(66882), IBM Tech. Report, 1989.","DOI":"10.1145\/72935.72937"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"R. J. Anderson and G. L. Miller. Deterministic parallel list ranking. In Proc. 3rd AWOC, pages 81\u201390, 1988.","DOI":"10.1007\/BFb0040376"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"R. Cole. Parallel merge sort. In Proc. 27th Annual IEEE Symp. on Foundations of Computer Science, pages 511\u2013516, 1986.","DOI":"10.1109\/SFCS.1986.41"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin. Approximate parallel scheduling, part i: the basic technique with applications to optimal parallel list ranking in logarithmic time. SIAM J. Comput, 17:128\u2013142, 1988.","journal-title":"SIAM J. Comput"},{"key":"2_CR6","unstructured":"R. Cypher. Efficient communication in massively parallel computers. PhD thesis, University of Washington, 1989. Department of Computer Scienceeig."},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"R. Cypher and C. G. Plaxton. Deterministic sorting in nearly logarithmic time on the hypercube and related computers. In Proc. 15th Annual ACM Symp. on Theory of Computing, pages 193\u2013203, 1990.","DOI":"10.1145\/100216.100240"},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0020-0190(89)90023-9","volume":"32","author":"A. M. Gibbons","year":"1989","unstructured":"A. M. Gibbons and Y.N. Srikant. A class of problems efficiently solvable on mesh-connected computers including dynamic expression evaluation. Information Processing Letters, 32:305\u2013311, 1989.","journal-title":"Information Processing Letters"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1145\/62.322423","volume":"31","author":"A. Gottlieb","year":"1984","unstructured":"A. Gottlieb and C. P. Kruskal. Complexity results for permuting data and other computations on parallel processors. JACM, 31:193\u2013209, 1984.","journal-title":"JACM"},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/0743-7315(89)90005-1","volume":"6","author":"Y. Han","year":"1989","unstructured":"Y. Han. Parallel algorithms for computing linked list prefix. J. of Parallel and Distributed Computing, 6:537\u2013357, 1989.","journal-title":"J. of Parallel and Distributed Computing"},{"key":"2_CR11","unstructured":"R. Karp and V. Ramachandran. A survey of parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science, 1988. Ed. J. van Leeuwen, North Holland, to appear."},{"key":"2_CR12","unstructured":"C. P. Kruskal, T. Madej, and L. Rudolph. Parallel prefix on fully connected direct connection machine. In Proc. International Conference on Parallel Processing, pages 278\u2013283, 1986."},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir. The power of parallel prefix. IEEE Transactions on Computers, pages 965\u2013968, 1985.","DOI":"10.1109\/TC.1985.6312202"},{"key":"2_CR14","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir. Efficient parallel algorithms for graph problems. In Proceedings International Conference on Parallel Processing, pages 869\u2013876, 1986."},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"C. P. Kruskal, L. Rudolph, and M. Snir. A complexity theory of efficient parallel algorithms. In Proc. 15th Annual ICALP. Springer Verlag Lecture Notes in Computer Science, Vol. 317, pp. 333\u2013346, July 1988. (Theoretical Computer Science, to appear 1989).","DOI":"10.1007\/3-540-19488-6_126"},{"key":"2_CR16","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1126\/science.231.4741.967","volume":"231","author":"D. J. Kuck","year":"1986","unstructured":"D. J. Kuck, E. S. Davidson, D. H. Lawrie, and A. H. Sameh. Parallel supercomputing today and the cedar approach. Science, 231:967\u2013974, 1986.","journal-title":"Science"},{"key":"2_CR17","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1109\/TC.1985.5009385","volume":"C-34","author":"F. T. Leighton","year":"1985","unstructured":"F. T. Leighton. Tight bounds on the complexity of parallel sorting. IEEE Transactions on Computers, C-34:344\u2013354, 1985.","journal-title":"IEEE Transactions on Computers"},{"key":"2_CR18","unstructured":"L. Meertens. Recurrent ultracomputers are not log n-fast. Technical Report 2, New York University, 1979. Ultracomputer."},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF00264615","volume":"21","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn and U. Vishkin. Randomized and deterministic simulations of prams by parallel machines with restricted granularity of parallel of parallel memories. Acta Informatica, 21:339\u2013374, 1984.","journal-title":"Acta Informatica"},{"key":"2_CR20","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1145\/358645.358660","volume":"24","author":"F. P. Preparata","year":"1981","unstructured":"F. P. Preparata and J. E. Vuillemin. The cube-connected cycles: A versatile network for parallel computation. CACM, 24:300\u2013309, 1981.","journal-title":"CACM"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"T. Leighton B. Maggs S. Rao. Universal packet routing algorithms. In Proc. 29th Annual IEEE Symp. on Foundations of Computer Science, pages 256\u2013271, 1988.","DOI":"10.21236\/ADA204273"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"J. H. Reif. An optimal parallel algorithm for integer sorting. In Proc. 26th Annual Symp. on Foundations of Computer Science, pages 496\u2013504, 1985.","DOI":"10.1109\/SFCS.1985.9"},{"key":"2_CR23","first-page":"637","volume":"46","author":"R. J. Swan","year":"1977","unstructured":"R. J. Swan, S. H. Fuller, and D. P. Siewiorek. Cm* \u2014 a modular, multi-processor. In Proc. AFIPS Conf., volume 46, pages 637\u2013644, 1977.","journal-title":"Proc. AFIPS Conf."},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. General purpose parallel architectures. In A handbook of Theoretical Computer Science. MIT Press, 1990. J. van Leeuwen (ed.).","DOI":"10.1016\/B978-0-444-88071-0.50023-0"},{"key":"2_CR25","unstructured":"R. A. Wagner and Y. Han. Parallel algorithms for bucket sorting and the data dependent prefix problem. In Proc. International Conference on Parallel Processing, pages 924\u2013930, 1986."},{"key":"2_CR26","unstructured":"J. C. Wyllie. The complexity of parallel computation. PhD thesis, Cornell University, 1979."}],"container-title":["Lecture Notes in Computer Science","PARLE '91 Parallel Architectures and Languages Europe"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0035093","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T21:20:34Z","timestamp":1683321634000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0035093"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540541516","9783540474715"],"references-count":26,"URL":"http:\/\/dx.doi.org\/10.1007\/bfb0035093","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}