{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T05:41:46Z","timestamp":1736314906999,"version":"3.32.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2006,5,1]],"date-time":"2006-05-01T00:00:00Z","timestamp":1146441600000},"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":[[2006,5]]},"DOI":"10.1007\/s00453-005-1189-3","type":"journal-article","created":{"date-parts":[[2006,2,23]],"date-time":"2006-02-23T15:28:58Z","timestamp":1140708538000},"page":"45-68","source":"Crossref","is-referenced-by-count":16,"title":["Direct routing: Algorithms and complexity"],"prefix":"10.1007","volume":"45","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":"Paul","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1189_CR1","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/s00453-002-1019-9","volume":"36","author":"M. Adler","year":"2003","unstructured":"M. Adler, S. Khanna, R. Rajaraman, and A. Ros\u00e9n. Time-constrained scheduling of weighted packets on trees and meshes.Algorithmica, 36:123\u2013152, 2003.","journal-title":"Algorithmica"},{"key":"1189_CR2","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/277651.277693","volume-title":"Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures","author":"M. Adler","year":"1998","unstructured":"M. Adler, A. L. Rosenberg, R. K. Sitaraman, and W. Unger. Scheduling time-constrained communication in linear networks. InProceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, pages 269\u2013278, Puerto Vallarta, Mexico, 1998."},{"issue":"3","key":"1189_CR3","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/S0895480192236628","volume":"7","author":"N. Alon","year":"1994","unstructured":"N. Alon, F. Chung, and R. Graham. Routing permutations on graphs via matching.SIAM Journal on Discrete Mathematics, 7(3):513\u2013530, 1994.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"1189_CR4","unstructured":"S. Alstrup, J. Holm, K. de Lichtenberg, and M. Thorup. Direct routing on trees. InProceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 98), pages 342\u2013349, 1998."},{"issue":"4","key":"1189_CR5","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/PL00009219","volume":"21","author":"I. Ben-Aroya","year":"1998","unstructured":"I. Ben-Aroya, D. D. Chinn, and A. Schuster. A lower bound for nearly minimal adaptive and hot potato algorithms.Algorithmica, 21(4):347\u2013376, August 1998.","journal-title":"Algorithmica"},{"issue":"1","key":"1189_CR6","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s002240000076","volume":"31","author":"A. Ben-Dor","year":"1998","unstructured":"A. Ben-Dor, S. Halevi, and A. Schuster. Potential function analysis of greedy hot-potato routing.Theory of Computing Systems, 31(1):41\u201361, Jan.\/Feb. 1998.","journal-title":"Theory of Computing Systems"},{"key":"1189_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"2001","unstructured":"B. Bollob\u00e1s.Random Graphs, second edition. Cambridge University Press, New York, 2001.","edition":"second edition"},{"key":"1189_CR8","doi-asserted-by":"crossref","unstructured":"A. Broder and E. Upfal. Dynamic deflection routing on arrays. InProceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 348\u2013358, May 1996.","DOI":"10.1145\/237814.237981"},{"key":"1189_CR9","doi-asserted-by":"crossref","unstructured":"C. Busch. \u00d5(Congestion + Dilation) hot-potato routing on leveled networks. InProceedings of the Fourteenth ACM Symposium on Parallel Algorithms and Architectures, pages 20\u201329, Aug. 2002.","DOI":"10.1145\/564870.564874"},{"key":"1189_CR10","doi-asserted-by":"crossref","unstructured":"C. Busch, M. Herlihy, and R. Wattenhofer. Hard-potato routing. InProceedings of the 32nd Annual ACM Symposium on Theory of Computing, pages 278\u2013285, May 2000.","DOI":"10.1145\/335305.338762"},{"key":"1189_CR11","first-page":"134","volume-title":"Proceedings of the 12th Annual European Symposium on Algorithms (ESA)","author":"C. Busch","year":"2004","unstructured":"C. Busch, M. Magdon-Ismail, M. Mavronicolas, and P. Spirakis. Direct routing: algorithms and complexity. In S. Albers and T. Radzik, editors,Proceedings of the 12th Annual European Symposium on Algorithms (ESA), pages 134\u2013145, Bergen, Norway, September 2004. Volume 3221 of Lecture Notes in Computer Science. Springer-Verlag, Berlin."},{"key":"1189_CR12","doi-asserted-by":"crossref","unstructured":"C. Busch, M. Magdon-Ismail, and J. Xi. Optimal oblivious path selection on the mesh. InProceedings of the International Parallel and Distributed Processing Symposium (IPDPS), pages 82\u201391, Denver, Colorado, April 2005.","DOI":"10.1109\/IPDPS.2005.311"},{"key":"1189_CR13","doi-asserted-by":"crossref","unstructured":"R. Cypher, F. M. auf der Heide, C. Scheideler, and B. V\u00f6cking. Universal algorithms for store-and-forward and wormhole routing. InProceedings of the 28th ACM Symposium on Theory of Computing, pages 356\u2013365, 1996.","DOI":"10.1145\/237814.237982"},{"key":"1189_CR14","doi-asserted-by":"crossref","unstructured":"U. Feige and J. Kilian. Zero knowledge and the chromatic number. InProceedings of the IEEE Conference on Computational Complexity, pages 278\u2013287, 1996.","DOI":"10.1109\/CCC.1996.507690"},{"key":"1189_CR15","doi-asserted-by":"crossref","unstructured":"U. Feige and P. Raghavan. Exact analysis of hot-potato routing. InProceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 553\u2013562, Pittsburgh, PA, Oct. 1992.","DOI":"10.1109\/SFCS.1992.267796"},{"key":"1189_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979."},{"key":"1189_CR17","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"D. S. Hochbaum","year":"1997","unstructured":"D. S. Hochbaum.Approximation Algorithms for NP-Hard Problems. PWS, Boston, MA, 1997."},{"key":"1189_CR18","doi-asserted-by":"crossref","unstructured":"C. Kaklamanis, D. Krizanc, and S. Rao. Hot-potato routing on processor arrays. InProceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 273\u2013282, Velen, Germany, June 30\u2013July 2, 1993.","DOI":"10.1145\/165231.376321"},{"key":"1189_CR19","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays \u2014 Trees \u2014 Hypercubes","author":"F. T. Leighton","year":"1992","unstructured":"F. T. Leighton.Introduction to Parallel Algorithms and Architectures: Arrays \u2014 Trees \u2014 Hypercubes. Morgan Kaufmann, San Mateo, CA, 1992."},{"key":"1189_CR20","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF01215349","volume":"14","author":"F. T. Leighton","year":"1994","unstructured":"F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job-scheduling inO(congestion +dilation) steps.Combinatorica, 14:167\u2013186, 1994.","journal-title":"Combinatorica"},{"key":"1189_CR21","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s004930050061","volume":"19","author":"T. Leighton","year":"1999","unstructured":"T. Leighton, B. Maggs, and A. W. Richa. Fast algorithms for finding O(congestion + dilation) packet routing schedules.Combinatorica, 19:375\u2013401, 1999.","journal-title":"Combinatorica"},{"key":"1189_CR22","doi-asserted-by":"crossref","unstructured":"B. M. Maggs, F. M. auf der Heide, B. Vocking, and M. Westermann. Exploiting locality for data management in systems of limited bandwidth. InProceedings of the IEEE Symposium on Foundations of Computer Science, pages 284\u2013293, 1997.","DOI":"10.1109\/SFCS.1997.646117"},{"key":"1189_CR23","first-page":"341","volume-title":"Proceedings of the Third Annual European Symposium on Algorithms","author":"F. Meyer Heide auf der","year":"1995","unstructured":"F. Meyer auf der Heide and C. Scheideler. Routing with bounded buffers and hot-potato routing in vertex-symmetric networks. In P. G. Spirakis, editor,Proceedings of the Third Annual European Symposium on Algorithms, pages 341\u2013354, Corfu, Greece, 25\u201327 Sept. 1995. Volume 979 of LNCS. Springer, Berlin."},{"issue":"1","key":"1189_CR24","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1006\/jagm.1998.0980","volume":"31","author":"F. Meyer Heide auf der","year":"1999","unstructured":"F. Meyer auf der Heide and B. V\u00f6cking. Shortest-path routing in arbitrary networks.Journal of Algorithms, 31(1):105\u2013131, Apr. 1999.","journal-title":"Journal of Algorithms"},{"key":"1189_CR25","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"2000","unstructured":"R. Motwani and P. Raghavan.Randomized Algorithms. Cambridge University Press, Cambridge, 2000."},{"key":"1189_CR26","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky and Y. Rabani. UniversalO (congestion+dilation+log1+\u025b N) local control packet switching algorithms. InProceedings of the 29th Annual ACM Symposium on the Theory of Computing, pages 644\u2013653, New York, May 1997.","DOI":"10.1145\/258533.258659"},{"issue":"2","key":"1189_CR27","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/S0304-3975(97)00049-2","volume":"185","author":"G. E. Pantziou","year":"1997","unstructured":"G. E. Pantziou, A. Roberts, and A. Symvonis. Many-to-many routing on trees via matchings.Theoretical Computer Science, 185(2):347\u2013377, 1997.","journal-title":"Theoretical Computer Science"},{"key":"1189_CR28","doi-asserted-by":"crossref","unstructured":"Y. Rabani and \u00c9. Tardos. Distributed packet switching in arbitrary networks. InProceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 366\u2013375, Philadelphia, PA, 22\u201324 May 1996.","DOI":"10.1145\/237814.237983"},{"issue":"4","key":"1189_CR29","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(95)00208-1","volume":"57","author":"A. Symvonis","year":"1996","unstructured":"A. Symvonis. Routing on trees.Information Processing Letters, 57(4):215\u2013223, 1996.","journal-title":"Information Processing Letters"},{"key":"1189_CR30","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1137\/0211027","volume":"11","author":"L. G. Valiant","year":"1982","unstructured":"L. G. Valiant. A scheme for fast parallel communication.SIAM Journal on Computing, 11:350\u2013361, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"1189_CR31","doi-asserted-by":"crossref","unstructured":"L. G. Valiant and G. J. Brebner. Universal schemes for parallel communication. InProceedings of the 13th Annual ACM Symposium on Theory of Computing, pages 263\u2013277, May 1981.","DOI":"10.1145\/800076.802479"},{"key":"1189_CR32","unstructured":"L. Zhang. Optimal bounds for matching routing on trees. InProceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 445\u2013453, 1997."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-005-1189-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-005-1189-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-005-1189-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T21:19:55Z","timestamp":1736284795000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-005-1189-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["1189"],"URL":"https:\/\/doi.org\/10.1007\/s00453-005-1189-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2006,5]]}}}