{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:41Z","timestamp":1725664181121},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_100","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:59:49Z","timestamp":1330257589000},"page":"503-514","source":"Crossref","is-referenced-by-count":4,"title":["Optimal average case sorting on arrays"],"prefix":"10.1007","author":[{"given":"Manfred","family":"Kunde","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus","family":"Reinhardt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"44_CR1","series-title":"Number 401 in Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/3-540-51859-2_18","volume-title":"Proc. of International Symposium on Optimal Algorithms","author":"B. S. Chlebus","year":"1989","unstructured":"B. S. Chlebus. Sorting within distance bound on a mesh-connected processor array. In H. Djidjev, editor, Proc. of International Symposium on Optimal Algorithms, Number 401 in Lecture Notes in Computer Science, pages 232\u2013238, Varna, Bulgaria, May\/June 1989. Springer."},{"key":"44_CR2","unstructured":"W. Feller. An Introduction to Probability Theory and its Applications, volume I. Wiley, 3d edition, 1968."},{"issue":"3","key":"44_CR3","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1109\/71.277787","volume":"5","author":"Q. P. Gu","year":"1994","unstructured":"Q. P. Gu and J. Gu. Algorithms and average time bounds of sorting on a meshconnected computer. IEEE Transactions on Parallel and Distributed Systems, 5(3):308\u2013315, March 1994.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"44_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T. Hagerup","year":"1990","unstructured":"T. Hagerup and C. R\u00fcb. A guided tour of Chernoff bounds. Information Processing Letters, 33:305\u2013308, 1990.","journal-title":"Information Processing Letters"},{"key":"44_CR5","doi-asserted-by":"crossref","unstructured":"M. Hofri. Probabilistic analysis of algorithms. Texts and Monographs in Computer Science. Springer-Verlag, 1987.","DOI":"10.1007\/978-1-4612-4800-2"},{"key":"44_CR6","doi-asserted-by":"crossref","unstructured":"M. Kaufmann, H. Schr\u00f6der, and J. F. Sibeyn. Routing and sorting on reconfigurable meshes. 1994. To appear in Parallel Processing Letters.","DOI":"10.1142\/S0129626495000084"},{"key":"44_CR7","unstructured":"M. Kaufmann, J. F. Sibeyn, and T. Suel. Derandomizing algorithms for routing and sorting on meshes. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms, pages 669\u2013679, 1994."},{"key":"44_CR8","unstructured":"D. E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, 2nd edition, 1969."},{"key":"44_CR9","unstructured":"D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, 1973."},{"key":"44_CR10","first-page":"272","volume-title":"Number 726 in Lecture Notes in Computer Science","author":"M. Kunde","year":"1993","unstructured":"M. Kunde. Block gossiping on grids and tori: Sorting and routing match the bisection bound deterministically. In T. Lengauer, editor, Proceedings of the 1st European Symposium on Algorithms, Number 726 in Lecture Notes in Computer Science, pages 272\u2013283, Bad Honnef, Federal Republic of Germany, September 1993. Springer."},{"key":"44_CR11","doi-asserted-by":"crossref","unstructured":"M. Kunde, R. Niedermeier, and P. Rossmanith. Faster sorting and routing on grids with diagonals. In P. Enjalbert, E. W. Mayr, and K. W. Wagner, editors, Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, pages 225\u2013236. Springer, 1994.","DOI":"10.1007\/3-540-57785-8_144"},{"key":"44_CR12","doi-asserted-by":"crossref","unstructured":"T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, 1992.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"44_CR13","doi-asserted-by":"crossref","unstructured":"T. Leighton. Methods for message routing in parallel machines. In Proceedings of the 24th ACM Symposium on Theory of Computing, pages 77\u201396, 1992.","DOI":"10.1145\/129712.129721"},{"issue":"6","key":"44_CR14","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1109\/12.277290","volume":"42","author":"R. Miller","year":"1993","unstructured":"R. Miller, V. K. Prasanna-Kumar, D. I. Reisis, and Q. F. Stout. Parallel computation on reconfigurable meshes. IEEE Transactions on Computers, 42(6):678\u2013692, June 1993.","journal-title":"IEEE Transactions on Computers"}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_100.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:25:07Z","timestamp":1605630307000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_100","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}