{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:26Z","timestamp":1759638866227},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633976"},{"type":"electronic","value":"9783540695363"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63397-9_22","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T15:22:48Z","timestamp":1270480968000},"page":"284-295","source":"Crossref","is-referenced-by-count":4,"title":["Three-dimensional meshes are less powerful than two-dimensional ones in oblivious routing"],"prefix":"10.1007","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[]},{"given":"Eiji","family":"Miyano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"A. Bar-Noy, P. Raghavan, B. Schieber and H. Tamaki, \u201cFast deflection routing for packets and worms,\u201d In Proc. ACM Symposium on Principles of Distributed Computing, 75\u201386 (1993).","DOI":"10.1145\/164051.164062"},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(85)90008-X","volume":"30","author":"A. Borodin","year":"1985","unstructured":"A. Borodin and J.E. Hopcroft, \u201cRouting, merging, and sorting on parallel models of computation,\u201d J. Computer and System Sciences 30 (1985) 130\u2013145.","journal-title":"J. Computer and System Sciences"},{"key":"22_CR3","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0020-0190(93)90208-Q","volume":"45","author":"S. Cheung","year":"1993","unstructured":"S. Cheung and F.C.M. Lau, \u201cA lower bound for permutation routing on two-dimensional bused meshes,\u201d Information Processing Letters 45 (1993) 225\u2013228.","journal-title":"Information Processing Letters"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"D.D. Chinn, T. Leighton and M. Tompa, \u201cMinimal adaptive routing on the mesh with bounded queue size,\u201d In Proc. 1994 ACM Symp. on Parallel Algorithms and Architectures (1994) 354\u2013363.","DOI":"10.1145\/181014.181451"},{"issue":"4","key":"22_CR5","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1109\/71.372798","volume":"6","author":"Q.P. Gu","year":"1995","unstructured":"Q.P. Gu and J. Gu, \u201cTwo packet routing algorithms on a mesh-connected computer,\u201d IEEE Trans. on Parallel and Distributed Systems, Vol. 6, No. 4 (1995) 436\u2013440.","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"key":"22_CR6","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1006\/jagm.1996.0030","volume":"20","author":"K. Iwama","year":"1996","unstructured":"K. Iwama, E. Miyano and Y. Kambayashi, \u201cRouting problems on the mesh of buses,\u201d J. Algorithms 20 (1996) 613\u2013631.","journal-title":"J. Algorithms"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"K. Iwama and E. Miyano, \u201cOblivious routing algorithms on the mesh of buses,\u201d In Proc. 11th International Parallel Processing Symposium, (1997) 721\u2013727.","DOI":"10.1109\/IPPS.1997.580986"},{"key":"22_CR8","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF02090400","volume":"24","author":"C. Kaklamanis","year":"1991","unstructured":"C. Kaklamanis, D. Krizanc and A. Tsantilas, \u201cTight bounds for oblivious routing in the hypercube,\u201d Math. Systems Theory 24 (1991) 223\u2013232.","journal-title":"Math. Systems Theory"},{"key":"22_CR9","unstructured":"C. Kaklamanis and D. Krizanc, \u201cOptimal sorting on mesh-connected processor arrays,\u201d In Proc. 1991 ACM Symposium on Parallel Algorithms and Architectures, (1991) 17\u201328."},{"key":"22_CR10","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF00264359","volume":"24","author":"M. Kunde","year":"1987","unstructured":"M. Kunde, \u201cLower bounds for sorting on mesh-connected architectures,\u201d Acta Informatica, 24 (1987) 121\u2013130.","journal-title":"Acta Informatica"},{"key":"22_CR11","unstructured":"F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann (1992)."},{"key":"22_CR12","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF01294128","volume":"14","author":"F.T. Leighton","year":"1995","unstructured":"F.T. Leighton, F. Makedon and I. Tollis, \u201cA 2n-2 step algorithm for routing in an nxn array with constant queue sizes,\u201d Algorithmica 14 (1995) 291\u2013304.","journal-title":"Algorithmica"},{"key":"22_CR13","unstructured":"L.Y.T. Leung and S.M. Shende, \u201cPacket routing on square meshes with row and column buses,\u201d In Proc. 1989 ACM Symp. on Parallel Algorithms and Architectures (1989) 328\u2013335."},{"key":"22_CR14","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1006\/jpdc.1994.1018","volume":"20","author":"L.Y.T. Leung","year":"1994","unstructured":"L.Y.T. Leung and S.M. Shende, \u201cOn multidimensional packet routing for meshes with buses,\u201d J. Parallel and Distributed Computing 20 (1994) 187\u2013197.","journal-title":"J. Parallel and Distributed Computing"},{"key":"22_CR15","unstructured":"T. Nesson, Randomized, oblivious, minimal routing algorithms for multi-computers, Ph.D Thesis, Harvard University (1995)."},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"C.P. Schnorr and A. Shamir, \u201cAn optimal sorting algorithm for mesh-connected computers,\u201d In Proc. ACM Symp. on Theory of Computing, (1986) 255\u2013263.","DOI":"10.1145\/12130.12156"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"J.F. Sibeyn, M. Kaufmann and R. Raman, \u201cRandomized routing on meshes with buses,\u201d In Proc. European Symposium on Algorithms, (1993) 333\u2013344.","DOI":"10.1007\/3-540-57273-2_68"},{"key":"22_CR18","unstructured":"T. Suel, \u201cRouting and sorting on fixed topologies,\u201d Ph.D Thesis, The University of Texas at Austin (1994)."},{"key":"22_CR19","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/0743-7315(92)90108-Y","volume":"15","author":"S. Rajasekaran","year":"1992","unstructured":"S. Rajasekaran and R. Overholt, \u201cConstant queue routing on a mesh,\u201d J. Parallel and Distributed Comput., 15 (1992) 160\u2013166.","journal-title":"J. Parallel and Distributed Comput."},{"key":"22_CR20","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF01758834","volume":"8","author":"S. Rajasekaran","year":"1992","unstructured":"S. Rajasekaran and T. Tsantilas, \u201cOptimal routing algorithms for meshconnected processor arrays,\u201d Algorithmica 8 (1992) 21\u201338.","journal-title":"Algorithmica"},{"key":"22_CR21","unstructured":"M. Tompa, Lecture notes on message routing in parallel machines, Technical Report # 94-06-05, Department of Computer Science and Engineering, University of Washington (1994)."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63397-9_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,3]],"date-time":"2019-02-03T12:08:07Z","timestamp":1549195687000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63397-9_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633976","9783540695363"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-63397-9_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}