{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T06:15:15Z","timestamp":1743056115674,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642022494"},{"type":"electronic","value":"9783642022500"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02250-0_10","type":"book-chapter","created":{"date-parts":[[2009,11,17]],"date-time":"2009-11-17T11:17:06Z","timestamp":1258456626000},"page":"265-279","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Permutation Routing and (\u2113, k)-Routing on Plane Grids"],"prefix":"10.1007","author":[{"given":"Ignasi","family":"Sau","sequence":"first","affiliation":[]},{"given":"Janez","family":"\u017derovnik","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,11,9]]},"reference":[{"key":"10_CR1","unstructured":"Amini, O., Huc, F., Sau, I., \u017derovnik, J.: (\u2113, k)-Routing on Plane Grids. Rapport de Recherche 6480 INRIA (2008)"},{"issue":"3","key":"10_CR2","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J. Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM (JACM) 44(3), 486\u2013504 (1997)","journal-title":"Journal of the ACM (JACM)"},{"key":"10_CR3","first-page":"109","volume":"90","author":"J. Aspnes","year":"2006","unstructured":"Aspnes, J., Busch, C., Dolev, S., Fatourou, P., Georgiou, C., Shvartsman, A.: Eight Open Problems in Distributed Computing. Bulletin of the EATCS 90, 109\u2013126 (2006)","journal-title":"Bulletin of the EATCS"},{"key":"10_CR4","unstructured":"Awerbuch, B., Azar, Y.: Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation. In: 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 240\u2013249 (1994)"},{"issue":"3","key":"10_CR5","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/j.jcss.2004.04.010","volume":"69","author":"Y. Azar","year":"2004","unstructured":"Azar, Y., Cohen, E., Fiat, A., Kaplan, H., R\u00e4cke, H.: Optimal oblivious routing in polynomial time. Journal of Computer and System Sciences 69(3), 383\u2013394 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Borodin, A., Hopcroft, J.: Routing, merging and sorting on parallel models of computation. Proceedings of the fourteenth annual ACM symposium on Theory of computing pp. 338\u2013344 (1982)","DOI":"10.1145\/800070.802209"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Busch, C., Magdon-Ismail, M., Xi, J.: Oblivious routing on geometric networks. Proceedings of the 17th annual ACM symposium on Parallelism in algorithms and architectures pp. 316\u2013324 (2005)","DOI":"10.1145\/1073970.1074022"},{"key":"10_CR8","unstructured":"Busch, C., Magdon-Ismail, M., Xi, J.: Optimal oblivious path selection on the mesh. Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS 2005), Denver, Colorado, USA, April (2005)"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/S1383-7621(03)00025-0","volume":"48","author":"T. Dobravec","year":"2003","unstructured":"Dobravec, T., Robi\u010d, B., \u017derovnik, J.: Permutation routing in double-loop networks: design and empirical evaluation. Journal of Systems Architecture 48, 387\u2013402 (2003)","journal-title":"Journal of Systems Architecture"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/j.sysarc.2005.12.003","volume":"52","author":"T. Dobravec","year":"2006","unstructured":"Dobravec, T., \u017derovnik, J., Robi\u010d, B.: An optimal message routing algorithm for circulant networks. Journal of Systems Architecture 52, 298\u2013306 (2006)","journal-title":"Journal of Systems Architecture"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0166-218X(94)90180-5","volume":"53","author":"P. Fraigniaud","year":"1994","unstructured":"Fraigniaud, P., Lazard, E.: Methods and problems of communication in usual networks. Discrete Applied Mathematics 53, 79\u2013134 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1007\/3-540-48224-5_63","volume":"2076","author":"J. T. Havill","year":"2001","unstructured":"Havill, J. T.: Online Packet Routing on Linear Arrays and Rings. Lecture Notes in Computer Science 2076, 773\u2013784 (2001)","journal-title":"Lecture Notes in Computer Science"},{"issue":"3","key":"10_CR13","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1142\/S0129626497000279","volume":"7","author":"F. Hwang","year":"1997","unstructured":"Hwang, F., Lin, T., Jan, R.: A Permutation Routing Algorithm for Double Loop Network. Parallel Processing Letters 7(3), 259\u2013265 (1997)","journal-title":"Parallel Processing Letters"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0304-3975(00)00279-6","volume":"270","author":"F. Hwang","year":"2002","unstructured":"Hwang, F., Yao, Y., Dasgupta, B.: Some permutation routing algorithms for low-dimensional hypercubes. Theoretical Computer Science 270, 111\u2013124 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"10_CR15","doi-asserted-by":"crossref","first-page":"17","DOI":"10.7155\/jgaa.00038","volume":"5","author":"K. Iwama","year":"2001","unstructured":"Iwama, K., Kambayashi, Y., Miyano, E.: New Bounds for Oblivious Mesh Routing. Journal of Graph Algorithms and Applications 5(5), 17\u201338 (2001)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jpdc.1999.1597","volume":"60","author":"K. Iwama","year":"2000","unstructured":"Iwama, K., Miyano, E.: Oblivious Routing Algorithms on the Mesh of Buses. Journal of Parallel and Distributed Computing 60, 137\u2013149 (2000)","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1006\/jagm.2001.1176","volume":"41","author":"K. Iwama","year":"2001","unstructured":"Iwama, K., Miyano, E.: An O($$\\sqrt{N}$$) Oblivious Routing Algorithm for Two-Dimensional Meshes of Constant Queue-Size. Journal of Algorithms 41, 262\u2013279 (2001)","journal-title":"Journal of Algorithms"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"1471","DOI":"10.1016\/j.jpdc.2005.04.004","volume":"65","author":"G. E. Jan","year":"2005","unstructured":"Jan, G. E., Lin, M. B.: Concentration, load balancing, partial permutation routing, and superconcentration on cube-connected cycles parallel computers. Journal of Parallel and Distributed Compututing 65, 1471\u20131482 (2005)","journal-title":"Journal of Parallel and Distributed Compututing"},{"issue":"1","key":"10_CR19","first-page":"223","volume":"24","author":"C. Kaklamanis","year":"1991","unstructured":"Kaklamanis, C., Krizanc, D., Tsantilas, T.: Tight bounds for oblivious routing in the hypercube. Theory of Computing Systems 24(1), 223\u2013232 (1991)","journal-title":"Theory of Computing Systems"},{"issue":"49","key":"10_CR20","first-page":"99","volume":"49","author":"S. Klav\u017ear","year":"2003","unstructured":"Klav\u017ear, S., Vesel, A., \u017digert, P.: On resonance graphs of catacondensed hexagonal graphs: structure, coding, and Hamiltonian path algorithm. MATCH Communications in Mathematical and in Computer Chemistry 49(49), 99\u2013116 (2003)","journal-title":"MATCH Communications in Mathematical and in Computer Chemistry"},{"key":"10_CR21","unstructured":"Kranakis, E., Sing, H., Urrutia, J.: Compas Routing in Geometric Graphs. In: 11th Canadian Conference of Computational Geometry, pp. 51\u201354 (1999)"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Kunde, M., Niedermeier, R., Rossmanith, P.: Faster sorting and routing on grids with diagonals. In: 11th Symposium of Theoretical Computer Science, 775, pp. 225\u2013236. Lecture Notes on Computer Science (1994)","DOI":"10.1007\/3-540-57785-8_144"},{"key":"10_CR23","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/0743-7315(91)90120-X","volume":"11","author":"M. Kunde","year":"1991","unstructured":"Kunde, M., Tensi, T.: (k\u2013k) Routing on Multidimensional Mesh-Connected Arrays. Journal of Parallel and Distributed Computing 11, 146\u2013155 (1991)","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Leighton, F., Maggs, B. M., Richa, A. W.: Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules. In: 28th Annual Hawaii International Conference on System Sciences, pp. 555\u2013563 (1995)","DOI":"10.21236\/ADA311323"},{"issue":"2","key":"10_CR25","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF01215349","volume":"14","author":"F. T. Leighton","year":"1994","unstructured":"Leighton, F. T., Maggs, B. M., Rao, S. B.: Packet Routing and Job-Shop Scheduling in O(congestion + dilation) Steps. Combinatorica 14(2), 167\u2013186 (1994)","journal-title":"Combinatorica"},{"key":"10_CR26","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes.","author":"T. Leighton","year":"1992","unstructured":"Leighton, T.: Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes. Morgan-Kaufman, San Mateo, California (1992)"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Leighton, T., Maggs, B., Rao, S.: Universal packet routing algorithms. In: 29th Annual Symposium on Foundations of Computer Science (FOCS), pp. 256\u2013269 (1988)","DOI":"10.1109\/SFCS.1988.21942"},{"key":"10_CR28","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF01294128","volume":"14","author":"T. Leighton","year":"1995","unstructured":"Leighton, T., Makedon, F., Tollis, I. G.: A 2n \u2013 2 Step Algorithm for Routing in an n \u00d7 n Array with Constant-Size Queues. Algorithmica 14, 291\u2013304 (1995)","journal-title":"Algorithmica"},{"key":"10_CR29","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1142\/S0219265901000488","volume":"2","author":"A. Litman","year":"2001","unstructured":"Litman, A., Moran-Schein, S.: Fast, minimal, and oblivious routing algorithms on the mesh with bounded queues. Journal of Interconnection Networks 2, 445\u2013469 (2001)","journal-title":"Journal of Interconnection Networks"},{"issue":"24","key":"10_CR30","doi-asserted-by":"publisher","first-page":"1505","DOI":"10.1109\/CISS.2006.286378","volume":"22","author":"B. Maggs","year":"2006","unstructured":"Maggs, B.: A Survey of Congestion + Dilation Results for Packet Scheduling. 40th Annual Conference on Information Sciences and Systems 22(24), 1505\u20131510 (2006)","journal-title":"40th Annual Conference on Information Sciences and Systems"},{"key":"10_CR31","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0141-9331(93)90056-D","volume":"17","author":"F. Makedon","year":"1993","unstructured":"Makedon, F., Symvonis, A.: Optimal algorithms for the many-to-one routing problem on 2-dimensional meshes. Microprocessors and Microsystems 17, 361\u2013367 (1993)","journal-title":"Microprocessors and Microsystems"},{"issue":"9","key":"10_CR32","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1109\/TPDS.2002.1036069","volume":"13","author":"F. G. Nocetti","year":"2002","unstructured":"Nocetti, F. G., Stojmenovi\u0107, I., Zhang, J.: Addressing and Routing in Hexagonal Networks with Applications for Tracking Mobile Users and Connection Rerouting in Cellular Networks. IEEE Transactions on Parallel and Distributed Systems 13(9), 963\u2013971 (2002)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"10_CR33","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.tcs.2004.04.016","volume":"333","author":"A. Osterloh","year":"2005","unstructured":"Osterloh, A.: Optimal oblivious routing on d-dimensional Meshes. Theoretical Computer Science 333, 331\u2013346 (2005)","journal-title":"Theoretical Computer Science"},{"key":"10_CR34","first-page":"644","volume-title":"Universal O(congestion + dilation + log1+\u03b5 N) Local Control Packet Switching Algorithms.","author":"R. Ostrovsky","year":"1997","unstructured":"Ostrovsky, R., Rabani, Y.: Universal O(congestion + dilation + log1+\u03b5 N) Local Control Packet Switching Algorithms. In: 29th Annual ACM Symposium on the Theory of Computing, pp. 644\u2013653. New York (1997)"},{"key":"10_CR35","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1007\/3-540-44681-8_92","volume":"2150","author":"A. Pietracaprina","year":"2001","unstructured":"Pietracaprina, A., Pucci, G.: Optimal Many-to-One Routing on the Mesh with Constant Queues. Lecture Notes in Computer Science 2150, 645\u2013649 (2001)","journal-title":"Lecture Notes in Computer Science"},{"key":"10_CR36","unstructured":"R\u00e4cke, H.: Exploiting locality for data management in systems of limited bandwidth. In: 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 284\u2013293 (1997)"},{"key":"10_CR37","unstructured":"R\u00e4cke, H.: Minimizing congestion in general networks. In: 43rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 43\u201352 (2002)"},{"key":"10_CR38","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0743-7315(92)90108-Y","volume":"15","author":"S. Rajasekaran","year":"1992","unstructured":"Rajasekaran, S., Overholt, R.: Constant queue routing on a mesh. Journal of Parallel and Distributed Computing 15, 160\u2013166 (1992)","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"1","key":"10_CR39","first-page":"37","volume":"19","author":"B. Robi\u010d","year":"2000","unstructured":"Robi\u010d, B., \u017derovnik, J.: Minimum 2-terminal routing in 2-jump circulant graphs. Computers and Artificial Intelligence 19(1), 37\u201346 (2000)","journal-title":"Computers and Artificial Intelligence"},{"issue":"3","key":"10_CR40","first-page":"49","volume":"10","author":"I. Sau","year":"2008","unstructured":"Sau, I., \u017derovnik, J.: An Optimal Permutation Routing Algorithm on Full-Duplex Hexagonal Networks. Discrete Mathematics and Theoretical Computer Science 10(3), 49\u201362 (2008)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"10_CR41","doi-asserted-by":"crossref","unstructured":"Scheideler, C.: Universal Routing Strategies for Interconnection Networks. Springer (1998)","DOI":"10.1007\/BFb0052928"},{"issue":"3","key":"10_CR42","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1142\/S0129054197000185","volume":"8","author":"J. Sibeyn","year":"1997","unstructured":"Sibeyn, J.: Routing on Triangles, Tori and Honeycombs. International Journal of Foundations of Computer Science 8(3), 269\u2013287 (1997)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"10_CR43","doi-asserted-by":"crossref","unstructured":"Sibeyn, J., Kaufman, M.: Deterministic 1-k routing on meshes (with applications to worm-hole routing). In: LNCS (ed.) 11th Symposium on Theoretical Aspects of Computer Science, vol. 775, pp. 237\u2013248 (1994)","DOI":"10.1007\/3-540-57785-8_145"},{"issue":"1","key":"10_CR44","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1006\/jagm.1995.0804","volume":"22","author":"J. F. Sibeyn","year":"1997","unstructured":"Sibeyn, J. F., Chlebus, B. S., Kaufmann, M.: Deterministic Permutation Routing on Meshes. Journal of Algorithms 22(1), 111\u2013141 (1997)","journal-title":"Journal of Algorithms"},{"key":"10_CR45","doi-asserted-by":"crossref","unstructured":"Srinivasan, A., Teo, C. P.: A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria. In: STOC \u201997: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 636\u2013643. ACM, New York, NY, USA (1997). DOI http:\/\/doi.acm.org\/10.1145\/258533.258658","DOI":"10.1145\/258533.258658"},{"issue":"10","key":"10_CR46","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1109\/71.629486","volume":"8","author":"I. Stojmenovi\u0107","year":"1997","unstructured":"Stojmenovi\u0107, I.: Honeycomb Networks: Topological Properties and Communication Algorithms. IEEE Transactions on Parallel and Distributed Systems 8(10), 1036\u20131042 (1997)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"10_CR47","doi-asserted-by":"crossref","unstructured":"Suel, T.: Routing and Sorting on Meshes with Row and Column Buses. In: Parallel Processing Symposium, vol. Eighth International Volume, pp. 411\u2013417 (1994)","DOI":"10.1109\/IPPS.1994.288269"},{"key":"10_CR48","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1021\/ci00024a002","volume":"35","author":"R. To\u0161i\u0107","year":"1995","unstructured":"To\u0161i\u0107, R., Masulovi\u0107, D., Stojmenovi\u0107, I., Brunvoll, J., Cyvin, B., Cyvin, S.: Enumeration of Polyhex Hydrocarbons up to h=17. Journal of Chemical Information and Computer Sciences 35, 181\u2013187 (1995)","journal-title":"Journal of Chemical Information and Computer Sciences"},{"key":"10_CR49","doi-asserted-by":"publisher","first-page":"1945","DOI":"10.1016\/S0167-8191(00)00063-6","volume":"26","author":"R. Trobec","year":"2000","unstructured":"Trobec, R.: Two-dimensional regular d-meshes. Parallel Computing 26, 1945\u20131953 (2000)","journal-title":"Parallel Computing"},{"key":"10_CR50","doi-asserted-by":"crossref","unstructured":"Valiant, L., Brebner, G.: Universal schemes for parallel communication. Proceedings of the thirteenth annual ACM symposium on Theory of computing pp. 263\u2013277 (1981)","DOI":"10.1145\/800076.802479"}],"container-title":["Texts in Theoretical Computer Science. An EATCS Series","Graphs and Algorithms in Communication Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02250-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T08:21:38Z","timestamp":1739434898000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-02250-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642022494","9783642022500"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02250-0_10","relation":{},"ISSN":["1862-4499"],"issn-type":[{"type":"print","value":"1862-4499"}],"subject":[],"published":{"date-parts":[[2009]]},"assertion":[{"value":"9 November 2009","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}