{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T07:22:21Z","timestamp":1742973741198,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642148484"},{"type":"electronic","value":"9783642148491"}],"license":[{"start":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T00:00:00Z","timestamp":1289174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2010,11,8]],"date-time":"2010-11-08T00:00:00Z","timestamp":1289174400000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-14849-1_13","type":"book-chapter","created":{"date-parts":[[2011,4,27]],"date-time":"2011-04-27T15:47:28Z","timestamp":1303919248000},"page":"381-406","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Oblivious Routing for Sensor Network Topologies"],"prefix":"10.1007","author":[{"given":"Costas","family":"Busch","sequence":"first","affiliation":[]},{"given":"Malik","family":"Magdon-Ismail","sequence":"additional","affiliation":[]},{"given":"Jing","family":"Xi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,11,8]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"J. Aspens, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts. Online load balancing with applications to machine scheduling and virtual circuit routing. In: Proceedings of the 25th ACM Symposium on Theory of Computing, pages 623\u2013631, ACM Press, San Diego, California, USA, 1993.","DOI":"10.1145\/167088.167248"},{"issue":"3","key":"13_CR2","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s00224-004-1124-z","volume":"37","author":"F. auf der Meyer Heide","year":"2004","unstructured":"F. Meyer auf der Heide, C. Schindelhauer, K. Volbert, and M. Gr\u00fcnewald. Congestion, dilation, and energy in radio networks. Theory of Computing Systems, 37(3):343\u2013370, 2004.","journal-title":"Theory of Computing Systems"},{"key":"13_CR3","unstructured":"B. Awerbuch and Y. Azar. Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation. In: Proceedings of 35th Annual Symposium on Foundations of Computer Science, pages 240\u2013249, Santa Fe, NM, 1994."},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Racke. Optimal oblivious routing in polynomial time. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), San Diego, CA, ACM Press. pages 383\u2013388, June 2003.","DOI":"10.1145\/780542.780599"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"M. Bienkowski, M. Korzeniowski, and H. R\u00e4cke. A practical algorithm for constructing oblivious routing schemes. In: Proceedings of the 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 24\u201333, ACM Press, San Diego, California, USA, June 2003.","DOI":"10.1145\/777412.777418"},{"key":"13_CR6","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 Science, 30:130\u2013145, 1985.","journal-title":"Journal of Computer and System Science"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"C. Busch, M. Magdon-Ismail, and J. Xi. Oblivious routing on geometric networks. In: Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Las Vegas, NV, pages 316\u2013324, July 2005.","DOI":"10.1145\/1073970.1074022"},{"issue":"5","key":"13_CR8","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1109\/TC.2008.23","volume":"57","author":"C. Busch","year":"2008","unstructured":"C. Busch, M. Magdon-Ismail, and J. Xi. Optimal oblivious path selection on the mesh. IEEE Transactions on Computers, 57(5):660\u2013671, May 2008.","journal-title":"IEEE Transactions on Computers"},{"issue":"5","key":"13_CR9","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.adhoc.2005.06.006","volume":"4","author":"I. Chatzigiannakis","year":"2006","unstructured":"I. Chatzigiannakis, T. Dimitriou, S. Nikoletseas, and P. Spirakis. A probabilistic algorithm for efficient and robust data propagation in wireless sensor networks. Ad Hoc Networks, 4(5): 621 \u2013 635, 2006.","journal-title":"Ad Hoc Networks"},{"issue":"1\u20132","key":"13_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1023\/B:MONE.0000048551.54039.f0","volume":"10","author":"I. Chatzigiannakis","year":"2005","unstructured":"I. Chatzigiannakis, S. Nikoletseas, and P. G. Spirakis. Efficient and robust protocols for local detection and propagation in smart dust networks. Mobile Networks and Applications, 10(1\u20132):133\u2013149, 2005.","journal-title":"Mobile Networks and Applications"},{"issue":"4","key":"13_CR11","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/j.adhoc.2005.01.003","volume":"4","author":"S. Dolev","year":"2006","unstructured":"S. Dolev, T. Herman, and L. Lahiani. Polygonal broadcast, secret maturity, and the firing sensors. Ad Hoc Networks, 4(4):447 \u2013 486, 2006.","journal-title":"Ad Hoc Networks"},{"issue":"6\u20137","key":"13_CR12","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.tcs.2008.10.006","volume":"410","author":"S. Dolev","year":"2009","unstructured":"S. Dolev and N. Tzachar. Empire of colonies: Self-stabilizing and self-organizing distributed algorithm. Theoretical Computer Science, 410(6\u20137):514\u2013532, 2009.","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"13_CR13","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/s11276-006-6529-y","volume":"12","author":"C. Efthymiou","year":"2006","unstructured":"C. Efthymiou, S. Nikoletseas, and J. Rolim. Energy balanced data propagation in wireless sensor networks. Wireless Networks, 12(6):691\u2013707, 2006.","journal-title":"Wireless Networks"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"J. Gao and L. Zhang. Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs. In PODC \u201904: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, New York, NY, pages 189\u2013196, 2004.","DOI":"10.1145\/1011767.1011795"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"C. Harrelson, K. Hildrum, and S. Rao. A polynomial-time tree decomposition to minimize congestion. In: Proceedings of the 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 34\u201343, June 2003.","DOI":"10.1145\/777412.777419"},{"issue":"1","key":"13_CR16","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/TNET.2002.808417","volume":"11","author":"C. Intanagonwiwat","year":"2003","unstructured":"C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva. Directed diffusion for wireless sensor networking. IEEE\/ACM Transmission Network, 11(1):2\u201316, 2003.","journal-title":"IEEE\/ACM Transmission Network"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"C. Kaklamanis, D. Krizanc, and T. Tsantilas. Tight bounds for oblivious routing in the hypercube. In: Proceedings of 2nd IEEE Symposium on Parallel and Distributed Processing (2nd SPAA 90), pages 31\u201336, Crete, Greece, July 1990.","DOI":"10.1145\/97444.97453"},{"key":"13_CR18","doi-asserted-by":"publisher","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 in $${O}(congestion+dilation)$$ steps. Combinatorica, 14:167\u2013186, 1994.","journal-title":"Combinatorica"},{"key":"13_CR19","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays - Trees - Hypercubes","author":"F. T. Leighton","year":"1992","unstructured":"F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays - Trees - Hypercubes. Morgan Kaufmann, San Mateo, CA, 1992."},{"key":"13_CR20","doi-asserted-by":"publisher","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":"13_CR21","doi-asserted-by":"crossref","unstructured":"B. M. Maggs, F. Meyer auf der Heide, B. V\u00f6cking, and M. Westerman. Exploiting locality in data management in systems of limited bandwidth. In: Proceedings of the 38th Annual Symposium on the Foundations of Computer Science, pages 284\u2013293, IEEE, Miami Beach, Florida, USA, 1997.","DOI":"10.1109\/SFCS.1997.646117"},{"issue":"1","key":"13_CR22","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1006\/jagm.1998.0980","volume":"31","author":"F auf der Meyer Heide","year":"1999","unstructured":"F. Meyer auf der Heide and Berthold V\u00f6cking. Shortest-path routing in arbitrary networks. Journal of Algorithms, 31(1):105\u2013131, April 1999.","journal-title":"Journal of Algorithms"},{"key":"13_CR23","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"2000","unstructured":"R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 2000."},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky and Y. Rabani. Universal O(congestion+dilation+$$\\log^{1+\\epsilon}{N})$$ local control packet switching algorithms. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, New York, NY, pages 644\u2013653, May 1997.","DOI":"10.1145\/258533.258659"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"L. Popa, A. Rostamizadeh, R. Karp, C. Papadimitriou, and I. Stoica. Balancing traffic load in wireless networks with curveball routing. In: MobiHoc, 2007.","DOI":"10.1145\/1288107.1288131"},{"key":"13_CR26","unstructured":"H. R\u00e4cke. Minimizing congestion in general networks. In: Proceedings of the 43rd Annual Symposium on the Foundations of Computer Science, pages 43\u201352, IEEE, Vancouver, Canada, November 2002."},{"key":"13_CR27","unstructured":"H. R\u00e4cke. Data management and routing in general networks. Phd thesis, University of Paderborn, Paderborn, Germany, 2003."},{"key":"13_CR28","doi-asserted-by":"crossref","unstructured":"H. R\u00e4cke. Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 255\u2013264, ACM Press, Victoria, British Columbia, Canada, May 2008.","DOI":"10.1145\/1374376.1374415"},{"key":"13_CR29","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"P. Raghavan and C. D. Thompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7:365\u2013374, 1987.","journal-title":"Combinatorica"},{"key":"13_CR30","unstructured":"C. Scheideler. Course notes. http:\/\/www14.in.tum.de\/lehre\/2005WS\/na\/index.html.en."},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"A. Srinivasan and C-P. Teo. A constant factor approximation algorithm for packet routing, and balancing local vs. global criteria. In: Proceedings of the ACM Symposium on the Theory of Computing (STOC), pages 636\u2013643, ACM Press, El Paso, Texas, USA, 1997.","DOI":"10.1145\/258533.258658"},{"key":"13_CR32","doi-asserted-by":"publisher","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":"13_CR33","doi-asserted-by":"crossref","unstructured":"L. G. Valiant and G. J. Brebner. Universal schemes for parallel communication. In: Proceedings of the 13th Annual ACM Symposium on Theory of Computing, pages 263\u2013277, Milwaukee, Wisconsin, USA, May 1981.","DOI":"10.1145\/800076.802479"},{"key":"13_CR34","volume-title":"Wireless Sensor Networks: An Information Processing Approach","author":"F. Zhao","year":"2004","unstructured":"F. Zhao and L. J. Guibas. Wireless Sensor Networks: An Information Processing Approach. Morgan Kaufmann, San Francisco, CA, USA, 2004."}],"container-title":["Monographs in Theoretical Computer Science. An EATCS Series","Theoretical Aspects of Distributed Computing in Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14849-1_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T08:36:33Z","timestamp":1741163793000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-14849-1_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,8]]},"ISBN":["9783642148484","9783642148491"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14849-1_13","relation":{},"ISSN":["1431-2654"],"issn-type":[{"type":"print","value":"1431-2654"}],"subject":[],"published":{"date-parts":[[2010,11,8]]},"assertion":[{"value":"8 November 2010","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}