{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:38:27Z","timestamp":1725467907218},"publisher-location":"New York, NY","reference-count":24,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9780387968186"},{"type":"electronic","value":"9780387347707"}],"license":[{"start":{"date-parts":[[1988,1,1]],"date-time":"1988-01-01T00:00:00Z","timestamp":567993600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/bfb0040401","type":"book-chapter","created":{"date-parts":[[2006,8,3]],"date-time":"2006-08-03T00:03:50Z","timestamp":1154563430000},"page":"339-350","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Network complexity of sorting and graph problems and simulating CRCW PRAMS by interconnection networks"],"prefix":"10.1007","author":[{"given":"Alok","family":"Aggarwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming-Deh A.","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, \"A Comparitive Study of X-Tree, Pyramids, and Related Machines\" Proc. of 25th Ann. Conference on Foundations of Computer Science, pp. 89\u201399, 1984.","DOI":"10.1109\/SFCS.1984.715905"},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"M. J. Atallah and S. E. Hambrusch, \"Solving Tree Problems on a Mesh Connected Processor Array,\" Proc. of the 26th Ann. Conference on the Foundations of Computer Science, pp. 222\u2013231, 1985.","DOI":"10.1109\/SFCS.1985.53"},{"key":"34_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Komlos, and E. Szemeredi, \"An O(n log n) Sorting Network,\" Proc. of 15th Ann. Symposium on Theory of Computing, pp. 1\u20139, 1983.","DOI":"10.1145\/800061.808726"},{"key":"34_CR4","unstructured":"B. Awerbuch, A. Israeli, and Y. Shiloach, \"Efficient Simulation of PRAM by an Ultracomputer,\" Technical Report 120, Israel Scientific Center, 1983."},{"key":"34_CR5","unstructured":"B. Awerbuch and Y. Shiloach, \"New Connectivity and MSF Algorithms for PRAMs and Ultracomputer,\" Technical Report 122, Israel Scientific Center, 1983."},{"issue":"2","key":"34_CR6","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1145\/62.322423","volume":"13","author":"A. Gottlieb","year":"1984","unstructured":"A. Gottlieb and C. P. Kruskal, \"Complexity Results for Permuting Data and Other Computations on Parallel Processors,\" Journal of the ACM, Vol. 13, No. 2, pp. 193\u2013209, 1984.","journal-title":"Journal of the ACM"},{"key":"34_CR7","unstructured":"P. S. Gopalakrishnan, L. N. Kanal, and I. V. Ramakrishnan, \"Finidng Connected Components on SIMD Computers,\" Tech. Report, Univ. of Maryland, 1985."},{"key":"34_CR8","unstructured":"P. S. Gopalakrishnan, L. N. Kanal, and I. V. Ramakrishnan, \"Computing Tree Functions on SIMD Computers,\" Technical Report, Univ. of Maryland, 1985."},{"key":"34_CR9","unstructured":"S. E. Hambrusch, \"The Complexity of Graph Problems in VLSI,\" Ph. D. Dissertation, Penn. State University, 1982."},{"key":"34_CR10","doi-asserted-by":"crossref","unstructured":"M.-D. A. Huang, \"Solving Some Graph Problems with Optimal or Near-Optimal Speedup on Mesh-of-Trees Networks,\" Proc. of the 26th Ann. Conference on the Foundations of Computer Science, pp. 232\u2013240, 1985.","DOI":"10.1109\/SFCS.1985.52"},{"key":"34_CR11","doi-asserted-by":"crossref","unstructured":"D. S. Hirschberg, A. K. Chandra, and D. V. Sarwate, \"Computing Connected Components on Parallel Computers,\" Comm. of ACM, pp. 461\u2013464, 1979.","DOI":"10.1145\/359138.359141"},{"key":"34_CR12","unstructured":"J. Ja'Ja, \"The VLSI Complexity of Graph Problems,\" Technical Report, Penn. State University, 1981."},{"issue":"4","key":"34_CR13","doi-asserted-by":"publisher","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 Trans. on Computers, Vol. C-34, No. 4, pp. 344\u2013354, 1985.","journal-title":"IEEE Trans. on Computers"},{"key":"34_CR14","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn and U. Vishkin, \"Randomized and Deterministic Simulations of PRAMs by Parallel Machines with Restricted Granularity of Parallel Memories,\" Proc. of the 9th Workshop on Graph Theoretic Concepts in Computer Science, Fachbereich Mathematik, Universitat Osnabruck, June 1983.","DOI":"10.1007\/BF00264615"},{"issue":"6","key":"34_CR15","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1109\/TC.1983.1676279","volume":"C-32","author":"D. Nath","year":"1983","unstructured":"D. Nath, S. N. Maheshwari, and P. C. P Bhatt, \"Efficient VLSI Networks for Parallel Processing Based on Orthogonal Trees,\" IEEE Trans. on Computers, Vol. C-32, No. 6, pp. 569\u2013581, 1983.","journal-title":"IEEE Trans. on Computers"},{"issue":"2","key":"34_CR16","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1109\/TC.1981.6312172","volume":"C-30","author":"D. Nassimi","year":"1980","unstructured":"D. Nassimi and S. Sahni, \"Data Broadcasting in SIMD Computers,\" IEEE Trans. on Computers, Vol. C-30, No. 2, pp. 101\u2013107, 1980.","journal-title":"IEEE Trans. on Computers"},{"issue":"5","key":"34_CR17","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1145\/358645.358660","volume":"24","author":"F. P. Preparata","year":"1981","unstructured":"F. P. Preparata and J. Vuillemin, \"The Cube-Connected Cycles: A Versatile Network for Parallel Computation,\" Comm. of ACM, Vol. 24, No. 5, pp. 300\u2013309, 1981.","journal-title":"Comm. of ACM"},{"key":"34_CR18","unstructured":"J. Reif and Q. Stout, Personal Communication, 1985."},{"key":"34_CR19","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/0196-6774(82)90013-X","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach and U. Vishkin, \"An O(log n) Parallel Connectivity Algorithm,\" Journal of Algorithms, Vol. 3, pp. 128\u2013146, 1982.","journal-title":"Journal of Algorithms"},{"key":"34_CR20","unstructured":"C. D. Thompson, \"A Complexity Theory for VLSI,\" Ph. D. Dissertation, Carnegie-Mellon University, 1980."},{"key":"34_CR21","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan and U. Vishkin, \"Finding Biconnected Components and Computing Tree Functions in Logarithmic Time,\" Proc. of the 25th Ann. Conference on Foundations of Computer Science, pp. 12\u201320, 1984.","DOI":"10.1109\/SFCS.1984.715896"},{"key":"34_CR22","doi-asserted-by":"crossref","unstructured":"E. Upfal, \"A Probabilistic Relation Between Desirable and Feasible Models of Parallel Computation,\" Proc. of the 16th Ann. Symposium on Theory of Computing, pp. 258\u2013265, 1984.","DOI":"10.1145\/800057.808689"},{"key":"34_CR23","doi-asserted-by":"crossref","unstructured":"E. Upfal and A. Wigderson, \"How to Share Memory in a Distributed System,\" Proc. of 25th Ann. Conference on the Foundations of Computer Science, pp. 171\u2013180, 1984.","DOI":"10.1109\/SFCS.1984.715913"},{"key":"34_CR24","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0196-6774(83)90033-0","volume":"4","author":"U. Vishkin","year":"1983","unstructured":"U. Vishkin, \"Implementation of Simultaneous Memory Address Access in Models That Forbid It,\" Journal of Algorithms, Vol. 4, pp. 45\u201350, 1983.","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0040401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T20:50:28Z","timestamp":1578516628000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0040401"}},"subtitle":["Preliminary version"],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9780387968186","9780387347707"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/bfb0040401","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}