{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:18:59Z","timestamp":1742617139716,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540616801"},{"type":"electronic","value":"9783540706670"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61680-2_76","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:11:18Z","timestamp":1330294278000},"page":"471-485","source":"Crossref","is-referenced-by-count":0,"title":["A lower bound for nearly minimal adaptive and hot potato algorithms"],"prefix":"10.1007","author":[{"given":"Ishai","family":"Ben-Aroya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donald D.","family":"Chinn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Assaf","family":"Schuster","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,6]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"A.S. Acampora and S.I.A. Shah. Multihop lightwave networks: a comparison of store-and-forward and hot-potato routing. In INFOCOM, pages 10\u201319. IEEE, 1991.","key":"35_CR1","DOI":"10.1109\/INFCOM.1991.147478"},{"doi-asserted-by":"crossref","unstructured":"A. Bar-Noy, P. Raghavan, B. Schieber, and H. Tamaki. Fast deflection routing for packets and worms. In Proceedings 12th Symposium on Principles of Distributed Computing, pages 75\u201386. ACM, 1993.","key":"35_CR2","DOI":"10.1145\/164051.164062"},{"key":"35_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TCOM.1964.1088883","volume":"12","author":"P. Baran","year":"1964","unstructured":"P. Baran. On distributed communications networks. IEEE Transactions on Communications, 12:1\u20139, 1964.","journal-title":"IEEE Transactions on Communications"},{"doi-asserted-by":"crossref","unstructured":"I. Ben-Aroya, I. Newman, and A. Schuster. Randomized single target hot potato routing. To appear in J. of Algorithms, 1996. (Also in Proceedings of the 3rd Israeli Symposium on Theory of Computing and Systems, January 1995, pages 20\u201329).","key":"35_CR4","DOI":"10.1109\/ISTCS.1995.377050"},{"issue":"1","key":"35_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01784239","volume":"9","author":"I. Ben-Aroya","year":"1995","unstructured":"I. Ben-Aroya, E. Tamar, and A. Schuster. Greedy hot-potato routing on the two-dimensional mesh. Distributed computing, 9(1):3\u201319, 1995. (Also in Proceedings of the 2nd European Symposium on Algorithms, Utrecht, 1994).","journal-title":"Distributed computing"},{"doi-asserted-by":"crossref","unstructured":"A. Ben-Dor, S. Halevi, and A. Schuster. Potential function analysis of greedy hotpotato routing. In Proceedings of the 13th Symposium on Principles of Distributed Computing, pages 225\u2013234, Los Angeles, August 1994. ACM. (Also Technion\/LPCR TR #9303, January 1993.).","key":"35_CR6","DOI":"10.1145\/197917.198098"},{"key":"35_CR7","doi-asserted-by":"publisher","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. Routing, merging, and sorting on parallel models of computation. Journal of Computer and System Sciences, 30:130\u2013145, 1985.","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"A. Borodin, Y. Rabani, and B. Schieber. Deterministic many-to-many hot potato routing. Technical Report RC 20107, IBM Watson Research Report, 1995.","key":"35_CR8"},{"unstructured":"J.T. Brassil and R.L. Cruz. Bounds on maximum delay in networks with deflection routing. In Proceedings of the 29th Allerton Conference on Communication, Control and Computing, pages 571\u2013580, 1991.","key":"35_CR9"},{"issue":"2","key":"35_CR10","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1006\/jpdc.1996.0052","volume":"34","author":"D.D. Chinn","year":"1996","unstructured":"D.D. Chinn, T. Leighton, and M. Tompa. Minimal adaptive routing on the mesh with bounded queue size. Journal of Parallel and Distributed Computing, 34(2):154\u2013170, 1996. Preliminary version in Proceedings of the 6th Symposium on Parallel Algorithms and Architectures, June 1994, pages 354\u2013363.","journal-title":"Journal of Parallel and Distributed Computing"},{"doi-asserted-by":"crossref","unstructured":"U. Feige. Observations on hot potato routing. In Proceedings of the 3rd Israeli Symposium on Theory of Computing and Systems, pages 30\u201339, January 1995.","key":"35_CR11","DOI":"10.1109\/ISTCS.1995.377049"},{"doi-asserted-by":"crossref","unstructured":"U. Feige and P. Raghavan. Exact analysis of hot-potato routing. In Proceedings of the 33rd Symposium on Foundations of Computer Science, pages 553\u2013562. IEEE, November 1992.","key":"35_CR12","DOI":"10.1109\/SFCS.1992.267796"},{"key":"35_CR13","first-page":"255","volume-title":"Teletraffic Analysis and Computer Performance Evaluation","author":"A.G. Greenberg","year":"1986","unstructured":"A.G. Greenberg and J. Goodman. Sharp approximate models of adaptive routing in mesh networks. In O.J. Boxma, J.W. Cohen, and H.C. Tijms, editors, Teletraffic Analysis and Computer Performance Evaluation, pages 255\u2013270. Elsevier, Amsterdam, 1986."},{"doi-asserted-by":"crossref","unstructured":"A.G. Greenberg and B. Hajek. Deflection routing in hypercube networks. IEEE Transactions on Communications, June 1992.","key":"35_CR14","DOI":"10.1109\/26.142797"},{"key":"35_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02311228","volume":"5","author":"B. Hajek","year":"1991","unstructured":"B. Hajek. Bounds on evacuation time for deflection routing. Distributed Computing, 5:1\u20136, 1991.","journal-title":"Distributed Computing"},{"doi-asserted-by":"crossref","unstructured":"C. Kaklamanis, D. Krizanc, and Satish Rao. Hot-potato routing on processor arrays. In Proceedings of the 5th Symposium on Parallel Algorithms and Architectures, pages 273\u2013282. ACM, 1993.","key":"35_CR16","DOI":"10.1145\/165231.376321"},{"doi-asserted-by":"crossref","unstructured":"M. Kaufmann, H. Lauer, and H. Schr\u00f6der. Fast deterministic hot-potato routing on meshes. In Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC), volume 834 of Lecture Notes in Computer Science, pages 333\u2013341. Springer-Verlag, 1994.","key":"35_CR17","DOI":"10.1007\/3-540-58325-4_197"},{"unstructured":"D.H. Lawrie and D.A. Padua. Analysis of message switching with shuffle-exchanges in multi-processors. Workshop on Interconnection Networks for Parallel and Distributed Computing, pages 116\u2013123, 1980.","key":"35_CR18"},{"doi-asserted-by":"crossref","unstructured":"N.F. Maxemchuk. Comparison of deflection and store and forward techniques in the manhattan street and shuffle exchange networks. In IEEE INFOCOM, pages 800\u2013809, 1989.","key":"35_CR19","DOI":"10.1109\/INFCOM.1989.101529"},{"issue":"11","key":"35_CR20","doi-asserted-by":"crossref","first-page":"1168","DOI":"10.1109\/71.476188","volume":"6","author":"I. Newman","year":"1995","unstructured":"I. Newman and A. Schuster. Hot-potato algorithms for permutation routing. IEEE Transactions on Parallel and Distributed Systems, 6(11):1168\u20131176, November 1995.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"doi-asserted-by":"crossref","unstructured":"J.Y. Ngai and C.L. Seitz. A framework for adaptive routing in multicomputer networks. In Proceedings of the 1st Symposium on Parallel Algorithms and Architectures, pages 1\u20139. ACM, 1989.","key":"35_CR21","DOI":"10.1145\/72935.72936"},{"doi-asserted-by":"crossref","unstructured":"T. Szymanski. An analysis of hot potato routing in a fiber optic packet switched hypercube. In IEEE INFOCOM, pages 918\u2013926, 1990.","key":"35_CR22","DOI":"10.1109\/INFCOM.1990.91340"},{"doi-asserted-by":"crossref","unstructured":"L.G. Valiant. Optimality of a two-phase strategy for routing in interconnection networks. IEEE Transactions on Computers, C-32(9), September 1983.","key":"35_CR23","DOI":"10.1109\/TC.1983.1676335"},{"doi-asserted-by":"crossref","unstructured":"Z. Zhang and A.S. Acampora. Performance analysis of multihop lightwave networks with hot potato routing and distance age priorities. In IEEE INFOCOM, pages 1012\u20131021, 1991.","key":"35_CR24","DOI":"10.1109\/INFCOM.1991.147615"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61680-2_76.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:23:52Z","timestamp":1742599432000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61680-2_76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616801","9783540706670"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-61680-2_76","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}