{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,29]],"date-time":"2023-04-29T13:10:10Z","timestamp":1682773810973},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[1989,9,1]],"date-time":"1989-09-01T00:00:00Z","timestamp":620611200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1989,9]]},"DOI":"10.1007\/bf00288975","type":"journal-article","created":{"date-parts":[[2004,10,4]],"date-time":"2004-10-04T17:10:14Z","timestamp":1096909814000},"page":"643-655","source":"Crossref","is-referenced-by-count":2,"title":["Time lower bounds for parallel sorting on a mesh-connected processor array"],"prefix":"10.1007","volume":"26","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":"CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: An O(N log N) sorting network. Proc. 15th ACM Symp. Theory Comput., pp. 1?9 (1983)","DOI":"10.1145\/800061.808726"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"Bilardi, G., Preparata, F.: A minimum area VLSI architecture for O(log N) time sorting. Proc. 16th Ann. ACM Symp. Theory Comput., pp. 67?70 (1984)","DOI":"10.1145\/800057.808666"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1145\/2514.2516","volume":"16","author":"D. Bitton","year":"1984","unstructured":"Bitton, D., Dewitt, D.T., Hsiao, D.K., Menon, J.: A taxonomy of parallel sorting. ACM Comput. Surv. 16, 287?318 (1984)","journal-title":"ACM Comput. Surv."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"Cole, R.: Parallel merge sort. 27th Symp. Found. Comput. Sci. IEEE, pp. 511?516 (1986)","DOI":"10.1109\/SFCS.1986.41"},{"key":"CR5","unstructured":"Han, Y., Igarashi, Y., Truszczynski, M.: Indexing functions and time lower bounds for sorting on a mesh-connected computer. Tech. Rep. No. 114-88, Dept. Comput. Sci., University of Kentucky"},{"key":"CR6","doi-asserted-by":"crossref","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 Inf. 24, 121?130 (1987)","journal-title":"Acta Inf."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"Kunde, M.: Bounds for l-selection and related problems on grids of processors. Proceedings of the Fourth International Workshop on Parallel Processing by Cellular Automata and Arrays, Berlin, GDR (Oct. 1988)","DOI":"10.1515\/9783112528365-021"},{"key":"CR8","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., Schr\u00f6der, H.: Systolic sorting on a mesh-connected network. IEEE Trans. Comput. C-34, 652?658 (1985)","journal-title":"IEEE Trans. Comput"},{"key":"CR9","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?354 (1985)","journal-title":"IEEE Trans. Comput."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"Ma, Y., Sen, S., Scherson, I.D.: The distance bound for sorting on mesh-connected processor arrays is tight. 27th Symp. Found. Comput. Sci. IEEE, pp. 255?263 (1986)","DOI":"10.1109\/SFCS.1986.54"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TC.1979.1675216","volume":"C-27","author":"D. Nassimi","year":"1979","unstructured":"Nassimi, D., Sahni, S.: Bitonic sort on a mesh-connected parallel computer. IEEE Trans. Comput. C-27, 2?7 (1979)","journal-title":"IEEE Trans. Comput"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1145\/7531.7532","volume":"34","author":"J.H. Reif","year":"1987","unstructured":"Reif, J.H., Valiant, L.G.: A logarithmic time sort for linear size networks. J. ACM 34, 60?76 (1987)","journal-title":"J. ACM"},{"key":"CR13","first-page":"41","volume":"AL84-68","author":"K. Sado","year":"1985","unstructured":"Sado, K., Igarashi, Y.: A divide-and-conquer method of the parallel sort. IECE of Japan, Tech. Commit. Autom. Lang. AL84-68, 41?50 (1985)","journal-title":"Tech. Commit. Autom. Lang."},{"key":"CR14","first-page":"41","volume":"AL84-68","author":"K. Sado","year":"1985","unstructured":"Sado, K., Igarashi, Y.: A fast pseudo-merge sorting algorithm. IECE of Japan, Tech. Commit, Autom. Lang. AL84-68, 41?50 (1985)","journal-title":"Tech. Commit, Autom. Lang."},{"key":"CR15","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., Igarashi, Y.: Fast parallel sorting on a mesh-connected processor array. In: Johnson, D.S., Nishizeki, T., Nozaki, A., Wilf, H.S. (eds.). Proc. of Japan-U.S. Joint Seminar, Discrete Algorithms and Complexity Theory, pp. 161?183. New York: Academic Press 1986"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1016\/0743-7315(86)90023-7","volume":"3","author":"K. Sado","year":"1986","unstructured":"Sado, K., Igarashi, Y.: Some parallel sorts on a mesh-connected processor array. J. Parallel Distrib. Comput. 3, 389?410 (1986)","journal-title":"J. Parallel Distrib. Comput."},{"key":"CR17","unstructured":"Scherson, I.D., Sen, S., Shamir, A.: Shear sort: A true two-dimensional sorting technique for VLSI networks. Proc. 1986 Int. Conf. Parallel Process, pp. 903?908 (1986)"},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"Schnorr, C.P., Shamir, A.: An optimal sorting algorithm for mesh-connected computers. Proc. 18-th ACM Symp. Theory Comput., pp. 255?263 (1986)","DOI":"10.1145\/12130.12156"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1145\/359461.359481","volume":"20","author":"C.D. Thompson","year":"1977","unstructured":"Thompson, C.D., Kung, H.T.: Sorting on a mesh-connected parallel computer. Commun. ACM 20, 263?271 (1977)","journal-title":"Commun. ACM"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1109\/TC.1983.1676178","volume":"C-32","author":"C.D. Thompson","year":"1984","unstructured":"Thompson, C.D.: The VLSI complexity of sorting. IEEE Trans. Comput. C-32, 1171?1184 (1984)","journal-title":"IEEE Trans. Comput."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00288975.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00288975\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00288975","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,29]],"date-time":"2023-04-29T12:30:21Z","timestamp":1682771421000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00288975"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,9]]},"references-count":20,"journal-issue":{"issue":"7","published-print":{"date-parts":[[1989,9]]}},"alternative-id":["BF00288975"],"URL":"https:\/\/doi.org\/10.1007\/bf00288975","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,9]]}}}