{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:22:21Z","timestamp":1763468541702,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,11,1]],"date-time":"2019-11-01T00:00:00Z","timestamp":1572566400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,1]],"date-time":"2019-11-01T00:00:00Z","timestamp":1572566400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"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"}]},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["1161","1367"],"award-info":[{"award-number":["1161","1367"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["757609"],"award-info":[{"award-number":["757609"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,5]]},"DOI":"10.1007\/s00453-019-00641-1","type":"journal-article","created":{"date-parts":[[2019,11,1]],"date-time":"2019-11-01T14:03:41Z","timestamp":1572617021000},"page":"1259-1276","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Reachability Oracles for Directed Transmission Graphs"],"prefix":"10.1007","volume":"82","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":[[2019,11,1]]},"reference":[{"issue":"2","key":"641_CR1","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.jalgor.2003.10.001","volume":"52","author":"J Alber","year":"2004","unstructured":"Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms 52(2), 134\u2013151 (2004)","journal-title":"J. Algorithms"},{"key":"641_CR2","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1007\/3-540-61680-2_79","volume-title":"Algorithms \u2014 ESA '96","author":"Srinivasa Arikati","year":"1996","unstructured":"Arikati, S., Chen, D.\u00a0Z., Chew, L.\u00a0P., Das, G., Smid, M., Zaroliagis, C.\u00a0D.: Planar spanners and approximate shortest path queries among obstacles in the plane. In: Proceedings of 4th Annual European Symposium Algorithms (ESA), pp. 514\u2013528 (1996)"},{"doi-asserted-by":"crossref","unstructured":"Chen, D.\u00a0Z., Xu, J.: Shortest path queries in planar graphs. In: Proceedings of 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 469\u2013478 (2000)","key":"641_CR3","DOI":"10.1145\/335305.335359"},{"issue":"5","key":"641_CR4","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338\u20131355 (2003)","journal-title":"SIAM J. Comput."},{"key":"641_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de\u00a0Berg","year":"2008","unstructured":"de\u00a0Berg, M., Cheong, O., van Kreveld, M., Overmars, M\u00a0.H.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"641_CR6","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/3-540-62559-3_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Hristo N. Djidjev","year":"1997","unstructured":"Djidjev, H.\u00a0N.: Efficient algorithms for shortest path queries in planar digraphs. In: Proceedings of 22nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 151\u2013165 (1996)"},{"issue":"6","key":"641_CR7","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"GN Federickson","year":"1987","unstructured":"Federickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Holm, J., Rotenberg, E., Thorup, M.: Planar reachability in linear space and constant time. In: Proceedings 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 370\u2013389 (2015)","key":"641_CR8","DOI":"10.1109\/FOCS.2015.30"},{"unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P.: Spanners and reachability oracles for directed transmission graphs. In: Proceedings of 31st International Symposium on Computational Geometry (SoCG), pp. 156\u2013170 (2015)","key":"641_CR9"},{"unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P.: Spanners for directed transmission graphs. arXiv:1601.07798 (2016)","key":"641_CR10"},{"issue":"3","key":"641_CR11","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/1807048.1807054","volume":"7","author":"D Peleg","year":"2010","unstructured":"Peleg, D., Roditty, L.: Localized spanner construction for ad hoc networks with variable transmission range. ACM Trans. Sens. Netw. 7(3), 25:1\u201325:14 (2010)","journal-title":"ACM Trans. Sens. Netw."},{"issue":"3","key":"641_CR12","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1137\/09075336X","volume":"40","author":"M P\u01cetra\u015fcu","year":"2011","unstructured":"P\u01cetra\u015fcu, M.: Unifying the landscape of cell-probe lower bounds. SIAM J. Comput. 40(3), 827\u2013847 (2011)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"641_CR13","doi-asserted-by":"publisher","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"},{"issue":"1","key":"641_CR14","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1109\/TNET.2008.926506","volume":"17","author":"P von Rickenbach","year":"2009","unstructured":"von Rickenbach, P., Wattenhofer, R., Zollinger, A.: Algorithmic models of interference in wireless ad hoc and sensor networks. IEEE\/ACM Trans. Netw. 17(1), 172\u2013185 (2009)","journal-title":"IEEE\/ACM Trans. Netw."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00641-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00641-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00641-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,31]],"date-time":"2020-10-31T00:09:49Z","timestamp":1604102989000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00641-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,1]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["641"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00641-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,11,1]]},"assertion":[{"value":"30 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}