{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:36:41Z","timestamp":1725475001237},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540496946"},{"type":"electronic","value":"9783540496960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11940128_65","type":"book-chapter","created":{"date-parts":[[2006,11,29]],"date-time":"2006-11-29T05:57:35Z","timestamp":1164779855000},"page":"650-659","source":"Crossref","is-referenced-by-count":2,"title":["Online Multi-path Routing in a Maze"],"prefix":"10.1007","author":[{"given":"Stefan","family":"R\u00fchrup","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Schindelhauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"65_CR1","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1137\/S0097539797330057","volume":"30","author":"D. Angluin","year":"2000","unstructured":"Angluin, D., Westbrook, J., Zhu, W.: Robot navigation with distance queries. SIAM Journal on Computing\u00a030(1), 110\u2013144 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"65_CR2","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BFb0029571","volume-title":"Online Algorithms: The State of the Art","author":"P. Berman","year":"1998","unstructured":"Berman, P.: On-line searching and navigation. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms: The State of the Art, pp. 232\u2013241. Springer, Heidelberg (1998)"},{"key":"65_CR3","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1137\/S0097539791194931","volume":"26","author":"A. Blum","year":"1997","unstructured":"Blum, A., Raghavan, P., Schieber, B.: Navigating in unfamiliar geometric terrain. SIAM Journal on Computing\u00a026, 110\u2013137 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"65_CR4","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"2-3","key":"65_CR5","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.tcs.2004.05.019","volume":"324","author":"P. Bose","year":"2004","unstructured":"Bose, P., Morin, P.: Competitive online routing in geometric graphs. Theoretical Computer Science\u00a0324(2-3), 273\u2013288 (2004)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"65_CR6","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1137\/S0097539700369387","volume":"33","author":"P. Bose","year":"2004","unstructured":"Bose, P., Morin, P.: Online routing in triangulations. SIAM Journal on Computing\u00a033(4), 937\u2013951 (2004)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"65_CR7","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1023\/A:1012319418150","volume":"7","author":"P. Bose","year":"2001","unstructured":"Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks\u00a07(6), 609\u2013616 (2001)","journal-title":"Wireless Networks"},{"issue":"16","key":"65_CR8","doi-asserted-by":"publisher","first-page":"1581","DOI":"10.1137\/S0097539793255011","volume":"26","author":"R.J. Cole","year":"1997","unstructured":"Cole, R.J., Maggs, B.M., Sitaraman, R.K.: Reconfiguring Arrays with Faults Part I: Worst-case Faults. SIAM Journal on Computing\u00a026(16), 1581\u20131611 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"65_CR9","first-page":"152","volume-title":"Mobile Computing","author":"D.B. Johnson","year":"1996","unstructured":"Johnson, D.B., Maltz, D.A.: Dynamic Source Routing in Ad Hoc Wireless Networks. In: Mobile Computing, pp. 152\u2013181. Kluwer, Dordrecht (1996)"},{"issue":"1","key":"65_CR10","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/S0097539796299540","volume":"30","author":"E. Koutsoupias","year":"2000","unstructured":"Koutsoupias, E., Papadimitriou, Ch.H.: Beyond competitive analysis. SIAM Journal on Computing\u00a030(1), 300\u2013317 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"65_CR11","unstructured":"Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proc. 11th Canadian Conference on Computational Geometry, pp. 51\u201354 (1999)"},{"key":"65_CR12","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically optimal geometric mobile ad-hoc routing. In: Proc. of the 6th Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 24\u201333 (2002)","DOI":"10.1145\/570810.570814"},{"issue":"5","key":"65_CR13","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1109\/9.1243","volume":"33","author":"C. Lucas","year":"1988","unstructured":"Lucas, C.: Comments on dynamic path planning for a mobile automation with limited information on the environment. IEEE Transactions on Automatic Control\u00a033(5), 511 (1988)","journal-title":"IEEE Transactions on Automatic Control"},{"issue":"2","key":"65_CR14","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/0885-064X(87)90025-2","volume":"3","author":"V.J. Lumelsky","year":"1987","unstructured":"Lumelsky, V.J.: Algorithmic and complexity issues of robot motion in an uncertain environment. J. Complex.\u00a03(2), 146\u2013182 (1987)","journal-title":"J. Complex."},{"key":"65_CR15","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/BF01840369","volume":"2","author":"V.J. Lumelsky","year":"1987","unstructured":"Lumelsky, V.J., Stepanov, A.A.: Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica\u00a02, 403\u2013430 (1987)","journal-title":"Algorithmica"},{"issue":"6","key":"65_CR16","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1109\/65.967595","volume":"15","author":"M. Mauve","year":"2001","unstructured":"Mauve, M., Widmer, J., Hartenstein, H.: A survey on position-based routing in mobile ad hoc networks. IEEE Network Magazine\u00a015(6), 30\u201339 (2001)","journal-title":"IEEE Network Magazine"},{"key":"65_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/BFb0035787","volume-title":"Automata, Languages and Programming","author":"C..H. Papadimitriou","year":"1989","unstructured":"Papadimitriou, Ch.H., Yannakakis, M.: Shortest paths without a map. In: Ronchi Della Rocca, S., Ausiello, G., Dezani-Ciancaglini, M. (eds.) ICALP 1989. LNCS, vol.\u00a0372, pp. 610\u2013620. Springer, Heidelberg (1989)"},{"key":"65_CR18","doi-asserted-by":"crossref","unstructured":"Perkins, C.E., Belding-Royer, E.M., Das, S.: Ad hoc on-demand distance vector (AODV) routing. IETF RFC 3561 (July 2003)","DOI":"10.17487\/rfc3561"},{"key":"65_CR19","doi-asserted-by":"crossref","unstructured":"Rao, N., Kareti, S., Shi, W., Iyenagar, S.: Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms (1993)","DOI":"10.2172\/10180101"},{"key":"65_CR20","unstructured":"R\u00fchrup, S.: Position-based Routing Strategies. PhD thesis, University of Paderborn (2006)"},{"key":"65_CR21","doi-asserted-by":"crossref","unstructured":"R\u00fchrup, S., Schindelhauer, C.: Competitive time and traffic analysis of position-based routing using a cell structure. In: Proc. of the 5th IEEE Int. Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN 2005), p. 248 (2005)","DOI":"10.1109\/IPDPS.2005.147"},{"key":"65_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/11561071_5","volume-title":"Algorithms \u2013 ESA 2005","author":"S. R\u00fchrup","year":"2005","unstructured":"R\u00fchrup, S., Schindelhauer, Ch.: Online routing in faulty mesh networks with sub-linear comparative time and traffic ratio. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 23\u201334. Springer, Heidelberg (2005)"},{"key":"65_CR23","doi-asserted-by":"crossref","unstructured":"R\u00fchrup, S., Schindelhauer, Ch.: Improved bounds for online multi-path routing in faulty mesh networks. Technical Report TR-RSFB-06-078, University of Paderborn (2006)","DOI":"10.1007\/11940128_65"},{"key":"65_CR24","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1109\/71.841751","volume":"11","author":"J. Wu","year":"2000","unstructured":"Wu, J.: Fault-tolerant adaptive and minimal routing in mesh-connected multicomputers using extended safety levels. IEEE Transactions on Parallel and Distributed Systems\u00a011, 149\u2013159 (2000)","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"65_CR25","unstructured":"Wu, J., Jiang, Z.: Extended minimal routing in 2-d meshes with faulty blocks. In: Proc. of the 1st Intl. Workshop on Assurance in Distributed Systems and Applications, pp. 49\u201355 (2002)"},{"key":"65_CR26","doi-asserted-by":"crossref","first-page":"714","DOI":"10.1007\/3-540-64359-1_737","volume-title":"Parallel and Distributed Processing","author":"L. Zakrevski","year":"1998","unstructured":"Zakrevski, L., Karpovsky, M.: Fault-tolerant message routing for multiprocessors. In: Parallel and Distributed Processing, pp. 714\u2013730. Springer, Heidelberg (1998)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11940128_65.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:50:07Z","timestamp":1619509807000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11940128_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540496946","9783540496960"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/11940128_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}