{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:37:23Z","timestamp":1725521843558},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540001423"},{"type":"electronic","value":"9783540361367"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36136-7_32","type":"book-chapter","created":{"date-parts":[[2008,11,25]],"date-time":"2008-11-25T14:07:11Z","timestamp":1227622031000},"page":"357-368","source":"Crossref","is-referenced-by-count":19,"title":["Approximate Distance Oracles Revisited"],"prefix":"10.1007","author":[{"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giri","family":"Narasimhan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,11,8]]},"reference":[{"key":"32_CR1","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D. Aingworth","year":"1999","unstructured":"D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28:1167\u20131181, 1999.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"S. Alstrup and J. Holm, Improved algorithms for finding level ancestors in dynamic trees. In Proc. 27th International Colloquium on Automata, Languages, and Programming, 2000.","DOI":"10.1007\/3-540-45022-X_8"},{"key":"32_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1007\/3-540-61680-2_79","volume-title":"Proc. 4th European Symposium on Algorithms","author":"S. Arikati","year":"1996","unstructured":"S. Arikati, D. Z. Chen, L. P. Chew, G. Das, M. Smid, and C. D. Zaroliagis. Planar spanners and approximate shortest path queries among obstacles in the plane. In Proc. 4th European Symposium on Algorithms, LNCS 1136, pp. 514\u2013528, 1996."},{"key":"32_CR4","unstructured":"D.Z. Chen. On the all-pairs Euclidean short path problem. In Proc. 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 292\u2013301, 1995."},{"key":"32_CR5","doi-asserted-by":"publisher","first-page":"1223","DOI":"10.1137\/S0097539796307194","volume":"29","author":"D. Z. Chen","year":"2000","unstructured":"D. Z. Chen, K. S. Klenk, and H.-Y. T. Tu. Shortest path queries among weighted obstacles in the rectilinear plane. SIAM Journal on Computing, 29:1223\u20131246, 2000.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR6","unstructured":"Y.-J. Chiang and J. S. B. Mitchell. Two-point Euclidean shortest path queries in the plane. In Proc. 10th ACM-SIAM Symposium on Discrete Algorithms, 1999."},{"key":"32_CR7","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794261295","volume":"28","author":"E. Cohen","year":"1998","unstructured":"E. Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing, 28:210\u2013236, 1998.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D. Dor","year":"2000","unstructured":"D. Dor, S. Halperin, and U. Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29:1740\u20131759, 2000.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"J. Gudmundsson, C. Levcopoulos, G. Narasimhan and M. Smid. Approximate Distance Oracles for Geometric graphs. In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, 2002.","DOI":"10.1007\/3-540-36136-7_32"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13:338\u2013355, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"48","DOI":"10.2307\/2033241","volume":"7","author":"J. B. Kruskal Jr","year":"1956","unstructured":"J. B. Kruskal, Jr. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. 7(1956):48\u201350, 1956.","journal-title":"Proc. Amer. Math. Soc."},{"issue":"4","key":"32_CR12","first-page":"446","volume":"6","author":"D. Krznaric","year":"1999","unstructured":"D. Krznaric, C. Levcopoulos and B. J. Nilsson. Minimum Spanning Trees in d Dimensions. Nordic Journal of Computing, 6(4):446\u2013461, 1999.","journal-title":"Nordic Journal of Computing"},{"key":"32_CR13","unstructured":"J. S. B. Mitchell. Shortest paths and networks. In Handbook of Discrete and Computational Geometry, pp. 445\u2013466. CRC Press LLC, 1997."},{"key":"32_CR14","doi-asserted-by":"crossref","unstructured":"M. Thorup and U. Zwick. Approximate distance oracles. In Proc. 33rd ACM Symposium on Theory of Computing, 2001.","DOI":"10.1145\/380752.380798"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36136-7_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T14:29:07Z","timestamp":1557930547000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36136-7_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540001423","9783540361367"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-36136-7_32","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}