{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T03:31:26Z","timestamp":1767843086143,"version":"3.49.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,3,30]],"date-time":"2017-03-30T00:00:00Z","timestamp":1490832000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["1161"],"award-info":[{"award-number":["1161"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MU 3501-1"],"award-info":[{"award-number":["MU 3501-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,3]]},"DOI":"10.1007\/s00453-017-0308-2","type":"journal-article","created":{"date-parts":[[2017,3,31]],"date-time":"2017-03-31T01:11:47Z","timestamp":1490922707000},"page":"830-848","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Routing in Unit Disk Graphs"],"prefix":"10.1007","volume":"80","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1948-5840","authenticated-orcid":false,"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[]},{"given":"Liam","family":"Roditty","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Seiferth","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,3,30]]},"reference":[{"issue":"6","key":"308_CR1","doi-asserted-by":"crossref","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. Wirel. Netw. 7(6), 609\u2013616 (2001)","journal-title":"Wirel. Netw."},{"issue":"1","key":"308_CR2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P Callahan","year":"1995","unstructured":"Callahan, P., Kosaraju, S.: A decomposition of multidimensional point sets with applications to $$k$$ k -nearest-neighbors and $$n$$ n -body potential fields. J. ACM 42(1), 67\u201390 (1995)","journal-title":"J. ACM"},{"key":"308_CR3","doi-asserted-by":"crossref","unstructured":"Chechik, S.: Compact routing schemes with improved stretch. In: Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 33\u201341 (2013)","DOI":"10.1145\/2484239.2484268"},{"issue":"1\u20133","key":"308_CR4","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1\u20133), 165\u2013177 (1990)","journal-title":"Discrete Math."},{"key":"308_CR5","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"308_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry Algorithms and Applications","author":"M Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"308_CR7","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in trees. In: Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP), pp. 757\u2013772 (2001)","DOI":"10.1007\/3-540-48224-5_62"},{"issue":"1","key":"308_CR8","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1137\/S0097539703436357","volume":"35","author":"J Gao","year":"2005","unstructured":"Gao, J., Zhang, L.: Well-separated pair decomposition for the unit-disk graph metric and its applications. SIAM J. Comput. 35(1), 151\u2013169 (2005)","journal-title":"SIAM J. Comput."},{"key":"308_CR9","doi-asserted-by":"crossref","unstructured":"Giordano, S., Stojmenovic, I.: Position based routing algorithms for ad hoc networks: a taxonomy. In: Cheng, X., Huang, X., Du, D.-Z. (eds.) Ad Hoc Wireless Networking, pp. 103\u2013136. Springer, New York (2004)","DOI":"10.1007\/978-1-4613-0223-0_4"},{"issue":"2","key":"308_CR10","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1137\/S0097539702409927","volume":"34","author":"A Gupta","year":"2004","unstructured":"Gupta, A., Kumar, A., Rastogi, R.: Traveling with a Pez dispenser (or, routing issues in MPLS). SIAM J. Comput. 34(2), 453\u2013474 (2004)","journal-title":"SIAM J. Comput."},{"key":"308_CR11","doi-asserted-by":"crossref","unstructured":"Karp, B., Kung, H.T.: GPSR: greedy perimeter stateless routing for wireless networks. In: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM), pp. 243\u2013254 (2000)","DOI":"10.1145\/345910.345953"},{"key":"308_CR12","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: of theory and practice. In: Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 63\u201372 (2003)","DOI":"10.1145\/872035.872044"},{"key":"308_CR13","volume-title":"Handbook of Discrete and Computational Geometry","author":"JSB Mitchell","year":"2017","unstructured":"Mitchell, J.S.B., Mulzer, W.: Proximity algorithms. In: Toth, C., O\u2019Rourke, J., Goodman, J. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn. CRC Press, Boca Raton (2017). (to appear)","edition":"3"},{"key":"308_CR14","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G Narasimhan","year":"2007","unstructured":"Narasimhan, G., Smid, M.H.M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)"},{"issue":"3","key":"308_CR15","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM 36(3), 510\u2013530 (1989)","journal-title":"J. ACM"},{"key":"308_CR16","doi-asserted-by":"crossref","unstructured":"Roditty, L., Tov, R.: New routing techniques and their applications. In: Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC), pp. 23\u201332 (2015)","DOI":"10.1145\/2767386.2767409"},{"issue":"1","key":"308_CR17","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1093\/comjnl\/28.1.5","volume":"28","author":"N Santoro","year":"1985","unstructured":"Santoro, N., Khatib, R.: Labelling and implicit routing in networks. Comput. J. 28(1), 5\u20138 (1985)","journal-title":"Comput. J."},{"issue":"6","key":"308_CR18","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M Thorup","year":"2004","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993\u20131024 (2004)","journal-title":"J. ACM"},{"key":"308_CR19","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"issue":"7","key":"308_CR20","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/j.comgeo.2012.01.015","volume":"45","author":"C Yan","year":"2012","unstructured":"Yan, C., Xiang, Y., Dragan, F.F.: Compact and low delay routing labeling scheme for unit disk graphs. Comput. Geom. 45(7), 305\u2013325 (2012)","journal-title":"Comput. Geom."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0308-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0308-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0308-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,4]],"date-time":"2020-10-04T18:08:24Z","timestamp":1601834904000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0308-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,30]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["308"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0308-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,30]]}}}