{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:16:51Z","timestamp":1725491811955},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75520-3_58","type":"book-chapter","created":{"date-parts":[[2007,9,13]],"date-time":"2007-09-13T23:46:33Z","timestamp":1189727193000},"page":"657-668","source":"Crossref","is-referenced-by-count":7,"title":["Fast and Compact Oracles for Approximate Distances in Planar Graphs"],"prefix":"10.1007","author":[{"given":"Laurent Flindt","family":"Muller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Zachariasen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"58_CR1","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. Journal of the ACM\u00a051, 993\u20131024 (2004)","journal-title":"Journal of the ACM"},{"key":"58_CR2","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A Separator Theorem for Planar Graphs. SIAM Journal on Applied Mathematics\u00a036, 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"58_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate Distance Oracles. Journal of the ACM\u00a052, 1\u201324 (2005)","journal-title":"Journal of the ACM"},{"key":"58_CR4","first-page":"156","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms","author":"A.V. Goldberg","year":"2005","unstructured":"Goldberg, A.V., Harrelson, C.: Computing the Shortest Path: A * Meets Graph Theory. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 156\u2013165. ACM Press, New York (2005)"},{"key":"58_CR5","unstructured":"Gutman, R.: Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In: Proceedings 6th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 100\u2013111 (2004)"},{"key":"58_CR6","doi-asserted-by":"crossref","unstructured":"Goldberg, A.V., Kaplan, H., Werneck, R.: Reach for A *: Efficient Point-to-Point Shortest Path Algorithms. In: Workshop on Algorithm Engineering and Experiments (2006)","DOI":"10.1137\/1.9781611972863.13"},{"key":"58_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/11561071_51","volume-title":"Algorithms \u2013 ESA 2005","author":"P. Sanders","year":"2005","unstructured":"Sanders, P., Schultes, D.: Highway Hierachies Hasten Exact Shortest Path Queries. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 568\u2013579. Springer, Heidelberg (2005)"},{"key":"58_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1007\/11841036_71","volume-title":"Algorithms \u2013 ESA 2006","author":"P. Sanders","year":"2006","unstructured":"Sanders, P., Schultes, D.: Engineering Highway Hierachies. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 804\u2013816. Springer, Heidelberg (2006)"},{"key":"58_CR9","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1126\/science.1137521","volume":"316","author":"H. Bast","year":"2007","unstructured":"Bast, H., Funke, S., Sanders, P., Schultes, D.: Fast Routing in Road Networks with Transit Nodes. Science\u00a0316, 566 (2007)","journal-title":"Science"},{"key":"58_CR10","doi-asserted-by":"crossref","unstructured":"Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In Transit to Constant Time Shortest-Path Queries in Road Networks. In: Proc. 9th Workshop on Algorithm Engineering and Experimentation (ALENEX) (2007)","DOI":"10.1137\/1.9781611972870.5"},{"key":"58_CR11","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1109\/SFCS.2001.959897","volume-title":"Proceedings of 42nd IEEE Symposium on Foundations of Computer Science","author":"J. Fakcharoenphol","year":"2001","unstructured":"Fakcharoenphol, J., Rao, S.: Planar Graphs, Negative Weight Edges, Shortest Paths, and Near Linear Time. In: Proceedings of 42nd IEEE Symposium on Foundations of Computer Science, pp. 232\u2013241. IEEE Computer Society Press, Los Alamitos (2001)"},{"key":"58_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C. Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance Labeling in Graphs. Journal of Algorithms\u00a053, 85\u2013112 (2004)","journal-title":"Journal of Algorithms"},{"key":"58_CR13","first-page":"820","volume-title":"Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms","author":"P. Klein","year":"2002","unstructured":"Klein, P.: Preprocessing an Undirected Planar Network to Enable Fast Approximate Distance Queries. In: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms, pp. 820\u2013827. ACM Press, New York (2002)"},{"key":"58_CR14","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"key":"58_CR15","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.: 9th DIMACS Implementation Challenge (2006), http:\/\/www.dis.uniroma1.it\/~challenge9\/"},{"key":"58_CR16","unstructured":"GMBH, A.S.S.: LEDA 5.2 (2007), http:\/\/www.algorithmic-solutions.com\/"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:23:00Z","timestamp":1619504580000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755197"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_58","relation":{},"subject":[]}}