{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:44Z","timestamp":1742617184408,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540616269"},{"type":"electronic","value":"9783540706335"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","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":[[1996]]},"DOI":"10.1007\/3-540-61626-8_34","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:05:20Z","timestamp":1330293920000},"page":"258-269","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient delay routing"],"prefix":"10.1007","author":[{"given":"Miriam","family":"Di Ianni","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"R. Aleliunas, \u201cRandomized parallel communication\u201d, Proc. of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 60\u201372, 1982.","key":"34_CR1","DOI":"10.1145\/800220.806683"},{"doi-asserted-by":"crossref","unstructured":"M. Bellare, M. Sudan, \u201cImproved non-approximability results\u201d, Proc. of the 26th Annual ACM Symposium on Theory of Computing, 184\u2013193, 1994.","key":"34_CR2","DOI":"10.1145\/195058.195129"},{"doi-asserted-by":"crossref","unstructured":"I. Cidon, S. Kutten, Y. Mansour, D. Peleg, \u201cGreedy packet scheduling\u201d, Proc. of 4th Workshop on Distributed Algorithms, 1990.","key":"34_CR3","DOI":"10.1007\/3-540-54099-7_12"},{"doi-asserted-by":"crossref","unstructured":"A. Clementi, M. Di Ianni, \u201cOptimum Schedule Problem in Store and Forward networks\u201d, Proc. of the IEEE INFOCOM'94, 1336\u20131343, 1994.","key":"34_CR4","DOI":"10.1109\/INFCOM.1994.337560"},{"doi-asserted-by":"crossref","unstructured":"A. Clementi, M. Di Ianni, \u201cOn the hardness of approximating optimum schedule problems in Store and Forward networks\u201d, to appear in IEEE-ACM Transactions on Networking, 1995.","key":"34_CR5","DOI":"10.1109\/90.491013"},{"key":"34_CR6","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey, D.S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, Freeman, San Francisco, 1979."},{"key":"34_CR7","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson, \u201cApproximation algorithms for combinatorial problems\u201d, Journal of Computer and System Sciences, 9, 256\u2013278, 1974.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"E. Koutsoupias, C. H. Papadimitriou, \u201cBeyond competitive analysis (on-line algorithms)\u201d, Proc.of the 35th IEEE Annual Symposium on Foundations of Computer Science, 394\u2013400, 1994.","key":"34_CR8","DOI":"10.1109\/SFCS.1994.365677"},{"key":"34_CR9","first-page":"411","volume-title":"Lecture Notes in Computer Science","author":"D. Krizanc","year":"1988","unstructured":"D. Krizanc, S. Rajasekaran and T. Tsantilis, \u201cOptimal routing algorithms for mesh-connected processor arrays\u201d, Lecture Notes in Computer Science, Springer-Verlag, New York, vol. 319, 411\u2013422, 1988."},{"key":"34_CR10","volume-title":"Introduction to parallel algorithms and architectures: arrays, trees, hypercubes","author":"T. Leighton","year":"1992","unstructured":"T. Leighton, Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, Morgan Kaufmann Publishers (San Mateo, Ca), 1992."},{"issue":"N.5","key":"34_CR11","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1109\/12.142684","volume":"41","author":"T. Leighton","year":"1992","unstructured":"T. Leighton and B. Maggs, \u201cFast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks\u201d, IEEE Trans. on Comput., 41, N. 5, 578\u2013587, 1992.","journal-title":"IEEE Trans. on Comput."},{"unstructured":"T. Leighton, F. Makedon and I. Tollis, \u201cA 2N-2 step algorithm for routing in an N \u00d7 N mesh\u201d, Proc. of the 1989 ACM Symposium on Parallel Algorithms and Architectures, 1989.","key":"34_CR12"},{"doi-asserted-by":"crossref","unstructured":"T. Leighton, B. Maggs, S. Rao, \u201cUniversal packet routing algorithms\u201d, Proc. of the 29th IEEE Annual Symposium on Foundations of Computer Science, 256\u2013269, 1988.","key":"34_CR13","DOI":"10.1109\/SFCS.1988.21942"},{"key":"34_CR14","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1006\/jagm.1994.1030","volume":"17","author":"T. Leighton","year":"1994","unstructured":"T. Leighton, B. Maggs, S. Rao, A.G Ranade \u201cRandomized routing and sorting on fixed-connection networks\u201d, Journal of Algorithms, 17, 157\u2013205, 1994.","journal-title":"Journal of Algorithms"},{"unstructured":"T. Leighton, B. Maggs, \u201cFast algorithms for finding O(congestion + dilation) packet routing schedules\u201d, Unpublished Manuscript, 1994.","key":"34_CR15"},{"key":"34_CR16","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF01215349","volume":"2","author":"T. Leighton","year":"1994","unstructured":"T. Leighton, B. Maggs, S. Rao, \u201cPacket routing and job-shop scheduling in O(congestion + dilation) steps\u201d, Combinatorica, 2, 167\u2013186, 1994.","journal-title":"Combinatorica"},{"key":"34_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01762110","volume":"3","author":"C.E. Leiserson","year":"1988","unstructured":"C.E. Leiserson and B. Maggs, \u201cCommunication-efficient parallel graph algorithms for distributed random-access machines\u201d, Algorithmica 3, 53\u201377, 1988.","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"C. Lund, M. Yannakakis, \u201cOn the hardness of approximating minimization problems\u201d, Proc. of 25th Annual ACM Symposium on Theory of Computing, pp. 286\u2013293, 1993.","key":"34_CR18","DOI":"10.1145\/167088.167172"},{"doi-asserted-by":"crossref","unstructured":"Y. Mansour, B. Patt-Shamir, \u201cGreedy packet scheduling on shortest paths\u201d, Proc. of the ACM PODC '91, 165\u2013175, 1991.","key":"34_CR19","DOI":"10.1145\/112600.112615"},{"doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide, B. V\u00f6cking, \u201cA packet routing protocol for arbitrary networks\u201d, Proc. of the 12th Symposium on Theoretical Aspects of Computer Sience, 291\u2013302, 1995.","key":"34_CR20","DOI":"10.1007\/3-540-59042-0_81"},{"doi-asserted-by":"crossref","unstructured":"N. Pippenger, \u201cParallel communication with limited buffers\u201d, Proc. of the 25th IEEE Annual Symposium on Foundations of Computer Science, 127\u2013136, 1984.","key":"34_CR21","DOI":"10.1109\/SFCS.1984.715909"},{"key":"34_CR22","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0022-0000(91)90005-P","volume":"42","author":"A.G. Ranade","year":"1991","unstructured":"A.G. Ranade, \u201cHow to emulate shared memory\u201d, Journal of Computer and System Sciences, 42, 307\u2013326, 1991.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"E. Upfal, \u201cEfficient schemes for parallel communication\u201d, Proc. of the ACM SIGACT-SIGOPS 1989 ACM Symposium on Principles of Distributed Computing, 55\u201359, 1982.","key":"34_CR23","DOI":"10.1145\/800220.806682"},{"key":"34_CR24","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/0211027","volume":"11\/2","author":"L.G. Valiant","year":"1982","unstructured":"L.G. Valiant, \u201cA schemes for fast parallel communication\u201d, SIAM Journal on Computing, 11\/2, 350\u2013361, 1982.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"L.G. Valiant and G.J. Brebner, \u201cUniversal schemes for parallel communication\u201d, Proc. 13th ACM Symposium on Theory of Computing, 263\u2013277, 1981","key":"34_CR25","DOI":"10.1145\/800076.802479"}],"container-title":["Lecture Notes in Computer Science","Euro-Par'96 Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61626-8_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:22:49Z","timestamp":1742599369000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61626-8_34"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616269","9783540706335"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-61626-8_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"8 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}