{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:38:09Z","timestamp":1725467889438},"publisher-location":"Berlin\/Heidelberg","reference-count":19,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"0387968180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0040410","type":"book-chapter","created":{"date-parts":[[2006,8,3]],"date-time":"2006-08-03T00:03:50Z","timestamp":1154563430000},"page":"434-443","source":"Crossref","is-referenced-by-count":3,"title":["Time lower bounds for parallel sorting on a mesh-connected processor array"],"prefix":"10.1007","author":[{"given":"Yijie","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshihide","family":"Igarashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"43_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., J. Koml\u00f3s, and E. Szemer\u00e9di. An O(NlogN) sorting network. Proc. 15th ACM Symp. on Theory of Computing, 1\u20139(1983).","DOI":"10.1145\/800061.808726"},{"key":"43_CR2","unstructured":"Bilardi, G., and Preparata, F.: A minimum area VLSI architecture for O(logN) time sorting, Proc. 16th Annual ACM Symp. on Theory of Computing, 67\u201370(1984)."},{"key":"43_CR3","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1145\/2514.2516","volume":"16","author":"D. Bitton","year":"1984","unstructured":"Bitton, D., Dewitt, D.T., Hsiao, D.K., and Menon, J.: A taxonomy of parallel sorting, ACM Computing Survey, 16, 287\u2013318 (1984).","journal-title":"ACM Computing Survey"},{"key":"43_CR4","unstructured":"Cole, R.: Parallel merge sort. 27th Symp. on Foundations of Comput. Sci., IEEE, 511\u2013516(1986)."},{"key":"43_CR5","unstructured":"Han, Y., Y. Igarashi, M. Truszczynski.: Indexing schemes and lower bounds for sorting on a mesh-connected computer. manuscript."},{"key":"43_CR6","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF00264359","volume":"24","author":"M. Kunde","year":"1987","unstructured":"Kunde, M.: Lower bounds for sorting on mesh-connected architectures. Acta Informatica, 24, 121\u2013130(1987).","journal-title":"Acta Informatica"},{"key":"43_CR7","doi-asserted-by":"crossref","first-page":"652","DOI":"10.1109\/TC.1985.1676603","volume":"C-34","author":"H.-W. Lang","year":"1985","unstructured":"Lang, H.-W., Schimmler, M., Schmech, H. and Schr\u00f6der, H.: Systolic sorting on a mesh-connected network, IEEE Trans. Comput., C-34, 652\u2013658(1985).","journal-title":"IEEE Trans. Comput."},{"key":"43_CR8","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1109\/TC.1985.5009385","volume":"C-34","author":"T. Leighton","year":"1985","unstructured":"Leighton, T.: Tight bounds on the complexity of parallel sorting. IEEE Trans. Comput., C-34, 344\u2013354, 1985.","journal-title":"IEEE Trans. Comput."},{"key":"43_CR9","unstructured":"Ma, Y., Sen, S. and Scherson, I.D.: The distance bound for sorting on mesh-connected processor arrays is tight. 27th Symp. on Foundations of Comput. Sci., IEEE, 255\u2013263(1986)."},{"key":"43_CR10","first-page":"-","volume":"27","author":"D. Nassimi","year":"1979","unstructured":"Nassimi, D., and Sahni, S.: Bitonic sort on a mesh-connected parallel computer, IEEE Trans. Comput., C-27(1979).","journal-title":"IEEE Trans. Comput., C"},{"key":"43_CR11","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1145\/7531.7532","volume":"34","author":"J.H. Reif","year":"1987","unstructured":"Reif, J.H. and Valiant L.G.: A logarithmic time sort for linear size networks, J. ACM, 34, 60\u201376(1987).","journal-title":"J. ACM"},{"key":"43_CR12","first-page":"41","volume":"AL84-68","author":"K. Sado","year":"1985","unstructured":"Sado, K. and Igarashi, Y.: A divide-and-conquer method of the parallel sort, IECE of Japan, Tech. Commit. of Automata and Languages, AL84-68, 41\u201350(1985).","journal-title":"IECE of Japan, Tech. Commit. of Automata and Languages"},{"key":"43_CR13","first-page":"41","volume":"AL84-68","author":"K. Sado","year":"1985","unstructured":"Sado, K. and Igarashi, Y.: A fast pseudo-merge sorting algorithm, IECE of Japan, Tech. Commit. of Automata and Languages, AL84-68, 41\u201350(1985).","journal-title":"IECE of Japan, Tech. Commit. of Automata and Languages"},{"key":"43_CR14","first-page":"161","volume-title":"Proc. of Japan-U.S. Joint Seminar, Discrete Algorithms and Complexity Theory","author":"K. Sado","year":"1986","unstructured":"Sado, K. and Igarashi, Y.: Fast parallel sorting on a mesh-connected processor array, Proc. of Japan-U.S. Joint Seminar, Discrete Algorithms and Complexity Theory(Johnson, D.S. et al. eds), Academic Press, New York, 161\u2013183(1986)."},{"key":"43_CR15","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1016\/0743-7315(86)90023-7","volume":"3","author":"K. Sado","year":"1986","unstructured":"Sado, K. and Igarashi, Y.: Some parallel sorts on a mesh-connected processor array, J. Parallel and Distributed Computing, Vol. 3, pp. 389\u2013410, 1986.","journal-title":"J. Parallel and Distributed Computing"},{"key":"43_CR16","unstructured":"Scherson, I.D., Sen, S. and Shamir, A.: Shear sort: A true two-dimensional sorting technique for VLSI networks, Proc. 1986 Int. Conf. on Parallel Processing, 903\u2013908(1986)."},{"key":"43_CR17","doi-asserted-by":"crossref","unstructured":"Schnorr, C.P. and Shamir, A.: An optimal sorting algorithm for mesh-connected computers, Proc. 18-th ACM Symp. on Theory of Computing, 255\u2013263(1986).","DOI":"10.1145\/12130.12156"},{"key":"43_CR18","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1145\/359461.359481","volume":"20","author":"C.D. Thompson","year":"1977","unstructured":"Thompson, C.D. and Kung, H.T.: Sorting on a mesh-connected parallel computer, Commun. ACM, 20, 263\u2013271(1977).","journal-title":"Commun. ACM"},{"key":"43_CR19","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1109\/TC.1983.1676178","volume":"C-32","author":"C.D. Thompson","year":"1983","unstructured":"Thompson, C.D.: The VLSI complexity of sorting, IEEE Trans. Comput. C-32, 1171\u20131184(1983).","journal-title":"IEEE Trans. Comput."}],"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\/BFb0040410.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:40:23Z","timestamp":1607550023000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0040410"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["0387968180"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0040410","relation":{},"subject":[]}}