{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T08:43:51Z","timestamp":1743151431615,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540229247"},{"type":"electronic","value":"9783540278665"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27866-5_109","type":"book-chapter","created":{"date-parts":[[2010,9,16]],"date-time":"2010-09-16T20:20:42Z","timestamp":1284668442000},"page":"820-827","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Near-Optimal Hot-Potato Routing on Trees"],"prefix":"10.1007","author":[{"given":"Costas","family":"Busch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Malik","family":"Magdon-Ismail","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marios","family":"Mavronicolas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roger","family":"Wattenhofer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"109_CR1","doi-asserted-by":"crossref","unstructured":"Acampora, A.S., Shah, S.I.A.: Multihop lightwave networks: a comparison of store-and-forward and hot-potato routing. In: Proc. IEEE INFOCOM, pp. 10\u201319 (1991)","DOI":"10.1109\/INFCOM.1991.147478"},{"issue":"3","key":"109_CR2","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/S0895480192236628","volume":"7","author":"N. Alon","year":"1994","unstructured":"Alon, N., Chung, F.R.K., Graham, R.L.: Routing permutations on graphs via matching. SIAM Journal on Discrete Mathematics\u00a07(3), 513\u2013530 (1994)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"109_CR3","unstructured":"Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Direct routing on trees. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pp. 342\u2013349 (1998)"},{"key":"109_CR4","doi-asserted-by":"crossref","unstructured":"Baran, P.: On distributed communications networks. IEEE Transactions on Communications, 1\u20139 (1964)","DOI":"10.1109\/TCOM.1964.1088883"},{"key":"109_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1007\/3-540-44520-X_122","volume-title":"Euro-Par 2000 Parallel Processing","author":"C. Bartzis","year":"2000","unstructured":"Bartzis, C., Caragiannis, I., Kaklamanis, C., Vergados, I.: Experimental evaluation of hot-potato routing algorithms on 2-dimensional processor arrays. In: Bode, A., Ludwig, T., Karl, W.C., Wism\u00fcller, R. (eds.) Euro-Par 2000. LNCS, vol.\u00a01900, pp. 877\u2013881. Springer, Heidelberg (2000)"},{"issue":"6","key":"109_CR6","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1109\/71.595575","volume":"8","author":"A. Borodin","year":"1997","unstructured":"Borodin, A., Rabani, Y., Schieber, B.: Deterministic many-to-many hot potato routing. IEEE Transactions on Parallel and Distributed Systems\u00a08(6), 587\u2013596 (1997)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"109_CR7","doi-asserted-by":"crossref","unstructured":"Busch, C.: \u00d5(Congestion + Dilation) hot-potato routing on leveled networks. In: Proceedings of the Fourteenth ACM Symposium on Parallel Algorithms and Architectures, August 2002, pp. 20\u201329 (2002)","DOI":"10.1145\/564870.564874"},{"key":"109_CR8","doi-asserted-by":"crossref","unstructured":"Busch, C., Herlihy, M., Wattenhofer, R.: Randomized greedy hot-potato routing. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 2000, pp. 458\u2013466 (2000)","DOI":"10.1145\/335305.338762"},{"key":"109_CR9","doi-asserted-by":"crossref","unstructured":"Busch, C., Magdon-Ismail, M., Mavranicolas, M., Spirakis, P.: Direct routing: Algorithms and Complexity. In: Proceedings of the 12th Annual European Symposium on Algorithms (ESA (September 2004)","DOI":"10.1007\/978-3-540-30140-0_14"},{"key":"109_CR10","volume-title":"The Connection Machine","author":"W.D. Hillis","year":"1985","unstructured":"Hillis, W.D.: The Connection Machine. MIT Press, Cambridge (1985)"},{"key":"109_CR11","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s004930050061","volume":"19","author":"T. Leighton","year":"1999","unstructured":"Leighton, T., Maggs, B., Richa, A.W.: Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica\u00a019, 375\u2013401 (1999)","journal-title":"Combinatorica"},{"key":"109_CR12","doi-asserted-by":"crossref","unstructured":"Maxemchuk, N.F.: Comparison of deflection and store and forward techniuques in the Manhattan street and shuffle exchange networks. In: Proc. IEEE INFOCOM, pp. 800\u2013809 (1989)","DOI":"10.1109\/INFCOM.1989.101529"},{"issue":"1","key":"109_CR13","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1006\/jagm.1998.0980","volume":"31","author":"F. Meyer auf der Heide","year":"1999","unstructured":"Meyer auf der Heide, F., V\u00f6cking, B.: Shortest-path routing in arbitrary networks. Journal of Algorithms\u00a031(1), 105\u2013131 (1999)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"109_CR14","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/S0304-3975(97)00049-2","volume":"185","author":"G.E. Pantziou","year":"1997","unstructured":"Pantziou, G.E., Roberts, A., Symvonis, A.: Many-to-many routing on trees via matchings. Theoretical Comp. Science\u00a0185(2), 347\u2013377 (1997)","journal-title":"Theoretical Comp. Science"},{"key":"109_CR15","unstructured":"Roberts, A., Symvonis, A., Wood, D.R.: Lower bounds for hotpotato permutation routing on trees. In: Proc. 7th Int. Coll. Structural Information and Communication Complexity, SIROCCO, June 2000, pp. 281\u2013295 (2000)"},{"key":"109_CR16","unstructured":"Seitz, C.L.: The Caltech Mosaic C: An experimental, fine-grain multicomputer. In: Proc. 4th Symp. on Parallel Algorithms and Architectures (June 1992); Keynote Speech"},{"key":"109_CR17","first-page":"241","volume-title":"Proceedings of the 4th Symp. Real Time Signal Processing IV","author":"B. Smith","year":"1981","unstructured":"Smith, B.: Architecture and applications of the HEP multiprocessor computer system. In: Proceedings of the 4th Symp. Real Time Signal Processing IV, pp. 241\u2013248. SPIE, San Jose (1981)"},{"key":"109_CR18","unstructured":"Zhang, L.: Optimal bounds for matching routing on trees. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 445\u2013453 (1997)"}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2004 Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27866-5_109","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T12:29:01Z","timestamp":1589891341000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27866-5_109"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540229247","9783540278665"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27866-5_109","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}