{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T22:46:31Z","timestamp":1736635591476,"version":"3.32.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1997,3]]},"DOI":"10.1007\/bf02523190","type":"journal-article","created":{"date-parts":[[2006,11,8]],"date-time":"2006-11-08T04:41:28Z","timestamp":1162960888000},"page":"224-244","source":"Crossref","is-referenced-by-count":14,"title":["Randomized multipacket routing and sorting on meshes"],"prefix":"10.1007","volume":"17","author":[{"given":"M.","family":"Kaufmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. F.","family":"Sibeyn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02523190_CR1","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff, H., A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations,Annals of Mathematical Statistics,23, 1952, 493\u2013507.","journal-title":"Annals of Mathematical Statistics"},{"key":"BF02523190_CR2","doi-asserted-by":"crossref","unstructured":"Chlebus, B. S., M. Kaufmann, J. F. Sibeyn, Deterministic Permutation Routing on Meshes,proc. 5th Symposium on Parallel and Distributed Processing, pp. 814\u2013821, IEEE, 1993.","DOI":"10.1109\/SPDP.1993.395448"},{"key":"BF02523190_CR3","doi-asserted-by":"crossref","unstructured":"Felperin, S., P. Raghavan, E. Upfal, A Theory of Wormhole Routing in Parallel Computers,Proc. 33rd Symposium on Foundations of Computer Science, pp. 563\u2013572, IEEE, 1992.","DOI":"10.1109\/SFCS.1992.267795"},{"key":"BF02523190_CR4","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T. Hagerup","year":"1990","unstructured":"Hagerup, T., C. R\u00fcb, A Guided Tour of Chernoff Bounds,Information Processing Letters,33, 1990, 305\u2013308.","journal-title":"Information Processing Letters"},{"key":"BF02523190_CR5","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e1j\u00e1","year":"1992","unstructured":"J\u00e1j\u00e1, J.,An Introduction to Parallel Algorithms, Addison-Wesley, Reading, MA, 1992."},{"key":"BF02523190_CR6","doi-asserted-by":"crossref","unstructured":"Kaklamanis, C., D. Krizanc, Optimal Sorting on Mesh-Connected Processor Arrays,Proc. 4th Symposium on Parallel Algorithms and Architectures, pp. 50\u201359, ACM, 1992.","DOI":"10.1145\/140901.140907"},{"key":"BF02523190_CR7","doi-asserted-by":"crossref","unstructured":"Kaklamanis, C., D. Krizanc, L. Narayanan, Th. Tsantilas, Randomized Sorting and Selection on Mesh Connected Processor Arrays,Proc. 3rd Symposium on Parallel Algorithms and Architectures, pp. 17\u201328, ACM, 1991.","DOI":"10.1145\/113379.113381"},{"key":"BF02523190_CR8","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., S. Rajasekaran, J. F. Sibeyn, Matching the Bisection Bound for Routing and Sorting on the Mesh,Proc. 4th Symposium on Parallel Algorithms and Architectures, pp. 31\u201340, ACM, 1992.","DOI":"10.1145\/140901.140905"},{"key":"BF02523190_CR9","series-title":"LNCS 621","first-page":"118","volume-title":"Proc. 3rd Scandinavian Workshop on Algorithm Theory","author":"M. Kaufmann","year":"1992","unstructured":"Kaufmann, M., J. F. Sibeyn, Optimal Multi-Packet Routing on the Torus,Proc. 3rd Scandinavian Workshop on Algorithm Theory, LNCS 621, pp. 118\u2013129, Springer-Verlag, Berlin, 1992."},{"key":"BF02523190_CR10","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., J. F. Sibeyn, Deterministic Routing on Circular Arrays,Proc. 4th Symposium on Parallel and Distributed Processing, pp. 376\u2013383, IEEE, 1992.","DOI":"10.1109\/SPDP.1992.242721"},{"key":"BF02523190_CR11","first-page":"141","volume":"32","author":"M. Kumar","year":"1983","unstructured":"Kumar, M., D. Hirschberg, An Efficient Implementation of Batcher's Odd-Even Merge Algorithm and its Application to Parallel Sorting Schemes,IEEE Transactions on Computers,32, 1983, 141\u2013150.","journal-title":"IEEE Transactions on Computers"},{"key":"BF02523190_CR12","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BFb0040409","volume-title":"Proc. VLSI Algorithms and Architectures","author":"M. Kunde","year":"1988","unstructured":"Kunde, M., Routing and Sorting on Mesh Connected Processor Arrays,Proc. VLSI Algorithms and Architectures, LNCS 319, pp. 423\u2013433, Springer-Verlag, Berlin, 1988."},{"key":"BF02523190_CR13","doi-asserted-by":"crossref","unstructured":"kunde, M., Concentrated Regular Data Streams on Grids; Sorting and Routing near to the Bisection Bound,Proc. 31st Symposium on Foundations of Computer Science, pp. 141\u2013150, IEEE, 1991.","DOI":"10.1109\/SFCS.1991.185363"},{"key":"BF02523190_CR14","doi-asserted-by":"crossref","unstructured":"Kunde, M. Balanced Routing: Towards the Distance Bound on Grids,Proc. 3rd Symposium on Parallel Algorithms and Architectures, pp. 260\u2013271, ACM, 1991.","DOI":"10.1145\/113379.113403"},{"key":"BF02523190_CR15","doi-asserted-by":"crossref","unstructured":"Kunde, M., T. Tensi, Multi-Packet Routing on Mesh Connected Processor Arrays,Proc. Symposium on Parallel Algorithms and Architectures, pp. 336\u2013343, ACM, 1989.","DOI":"10.1145\/72935.72971"},{"key":"BF02523190_CR16","doi-asserted-by":"crossref","unstructured":"Leighton, T., Average Case Analysis of Greedy Routing Algorithms on Arrays,Proc. 2nd Symposium on Parallel Algorithms and Architectures, pp. 2\u201310, ACM 1990.","DOI":"10.1145\/97444.97448"},{"key":"BF02523190_CR17","doi-asserted-by":"crossref","unstructured":"Leighton, T., F. Makedon, I. G. Tollis, A 2n\u20132 Step Algorithm for Routing in ann\u00d7n Array with Constant Size Queues,Proc. Symposium on Parallel Algorithms and Architectures, pp. 328\u2013335, ACM, 1989.","DOI":"10.1145\/72935.72970"},{"key":"BF02523190_CR18","doi-asserted-by":"crossref","unstructured":"Ma, Y., S. Sen, D. Scherson, The Distance Bound for Sorting on Mesh Connected Processor Arrays is Tight,Proc. 27th Symposium on Foundations of Computer Science, pp. 255\u2013263, IEEE, 1986.","DOI":"10.1109\/SFCS.1986.54"},{"key":"BF02523190_CR19","doi-asserted-by":"crossref","unstructured":"Makedon, F., A. Simvonis, On Bit Serial Packet Routing for the Mesh and the Torus,Proc. 3rd Symposium on Frontiers of Massively Parallel Computation, pp. 294\u2013302, IEEE, 1990.","DOI":"10.1109\/FMPC.1990.89475"},{"key":"BF02523190_CR20","series-title":"LNCS","first-page":"226","volume-title":"Proc. 1st International ACPC Conference","author":"F. Makedon","year":"1991","unstructured":"Makedon, F., A. Simvonis, Multipacket Ronting on Rings,Proc. 1st International ACPC Conference, LNCS 591, pp. 226\u2013237, Springer-Verlag, Berlin, 1991."},{"key":"BF02523190_CR21","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1006\/jpdc.1995.1127","volume":"30","author":"I. Newman","year":"1995","unstructured":"Newman, I., A. Schuster, Hot Potato Worm Routing via Store-and-Forward Packet Routing,Journal of Parallel and Distributed Computing,30, 1995, 76\u201384.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"BF02523190_CR22","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1016\/0743-7315(90)90083-2","volume":"9","author":"A. Park","year":"1990","unstructured":"Park, A., K. Balasubramanian, Reducing Communication Costs for Sorting on Mesh-Connected and Linearly Connected Parallel Computers,Journal of Parallel and Distributed Computing,9, 1990, 318\u2013322.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"BF02523190_CR23","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1006\/jagm.1995.1042","volume":"19","author":"S. Rajasekaran","year":"1995","unstructured":"Rajasekaran, S.,k-k Routing,k-k Sorting, and Cut-Through Routing on the Mesh,Journal of Algorithms,19, 1995, 361\u2013382.","journal-title":"Journal of Algorithms"},{"key":"BF02523190_CR24","doi-asserted-by":"crossref","unstructured":"Rajasekaran, S., M. Raghavachari, Optimal Randomized Algorithms for Multipacket and Cut Through Routing on the Mesh,Proc. 3rd Symposium on Parallel and Distributed Processing, IEEE, pp. 305\u2013311, 1991.","DOI":"10.1109\/SPDP.1991.218264"},{"key":"BF02523190_CR25","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF01758834","volume":"8","author":"S. Rajasekaran","year":"1992","unstructured":"Rajasekaran, S., Th. Tsantilas, Optimal Routing Algorithms for Mesh-Connected processor Arrays,Algorithmica,8, 1992, 21\u201338.","journal-title":"Algorithmica"},{"key":"BF02523190_CR26","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/7531.7532","volume":"34","author":"J. Reif","year":"1987","unstructured":"Reif, J., L. G. Valiant, A Logarithmic Time Sort for Linear Size Networks,Journal of the ACM,34, 1987, 68\u201376.","journal-title":"Journal of the ACM"},{"key":"BF02523190_CR27","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1137\/0214030","volume":"14","author":"R. Reischuk","year":"1985","unstructured":"Reischuk, R., Probabilistic Parallel Algorithms for Sorting and Selection,SIAM Journal on Computing,14, 1985, 396\u2013411.","journal-title":"SIAM Journal on Computing"},{"key":"BF02523190_CR28","doi-asserted-by":"crossref","unstructured":"Schnorr, C. P., A. Shamir, An Optimal Sorting Algorithm for Mesh Connected Computers,Proc. 18th Symposium on Theory of Computing, pp. 255\u2013263, ACM, 1986.","DOI":"10.1145\/12130.12156"},{"key":"BF02523190_CR29","doi-asserted-by":"crossref","unstructured":"Sibeyn, J. F., M. Kaufmann, Randomizedk-k Sorting on meshes, draft, 1992.","DOI":"10.1007\/3-540-57273-2_68"},{"key":"BF02523190_CR30","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1145\/359461.359481","volume":"20","author":"C. D. Thompson","year":"1977","unstructured":"Thompson, C. D., H. T. Kung, Sorting on a Mesh Connected Parallel Computer,Communications of the ACM,20, 1977, 263\u2013270.","journal-title":"Communications of the ACM"},{"issue":"8","key":"BF02523190_CR31","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"L. G. Valiant","year":"1990","unstructured":"Valiant, L. G., A bridging Model for Parallel Computation,Communications of the ACM,33(8), 1990, 103\u2013111.","journal-title":"Communications of the ACM"},{"key":"BF02523190_CR32","doi-asserted-by":"crossref","unstructured":"Valiant, L. G., G. J. Brebner, Universal Schemes for Parallel Communication,Proc. 13th Symposium on Theory of Computing, pp. 263\u2013277, ACM, 1981.","DOI":"10.1145\/800076.802479"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523190.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523190\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523190","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T22:19:32Z","timestamp":1736633972000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523190"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["BF02523190"],"URL":"https:\/\/doi.org\/10.1007\/bf02523190","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}