{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:59:14Z","timestamp":1725559154135},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241317"},{"type":"electronic","value":"9783540305514"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30551-4_7","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T14:15:37Z","timestamp":1279030537000},"page":"53-64","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Distance Oracles for Graphs with Dense Clusters"],"prefix":"10.1007","author":[{"given":"Mattias","family":"Andersson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","volume-title":"Complexity and Approximation \u2013 Combinatorial optimization problems and their approximability properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation \u2013 Combinatorial optimization problems and their approximability properties. Springer, Heidelberg (1999) ISBN 3-540-65431-3"},{"issue":"4","key":"7_CR2","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D. Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing\u00a028(4), 1167\u20131181 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Arikati, S., Chen, D.Z., Chew, L.P., Das, G., Smid, M., Zaroliagis, C.D.: Planar spanners and approximate shortest path queries among obstacles in the plane. In: Proc. 4th European Symposium on Algorithms, pp. 514\u2013528 (1996)","DOI":"10.1007\/3-540-61680-2_79"},{"issue":"6","key":"7_CR4","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S. Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching. Journal of the ACM\u00a045(6), 891\u2013923 (1998)","journal-title":"Journal of the ACM"},{"issue":"1","key":"7_CR5","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P.B. Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM\u00a042(1), 67\u201390 (1995)","journal-title":"Journal of the ACM"},{"key":"7_CR6","unstructured":"Chen, D.Z.: On the all-pairs Euclidean short path problem. In: Proc. 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 292\u2013301 (1995)"},{"issue":"1","key":"7_CR7","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794261295","volume":"28","author":"E. Cohen","year":"1998","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing\u00a028(1), 210\u2013236 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Dijkstra, E.W.: A Note on Two Problems in Connexion with Graphs. Numerische Mathmatik\u00a01 (1959)","DOI":"10.1007\/BF01386390"},{"issue":"5","key":"7_CR9","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D. Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM Journal on Computing\u00a029(5), 1740\u20131759 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR10","unstructured":"Eppstein, D., Hart, D.: Shortest Paths in an Arrangement with k Line Orientations. In: 10th ACM-SIAM Symposium on Discrete Algorithms, pp. 310\u2013316 (1999)"},{"issue":"3","key":"7_CR11","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM\u00a034(3), 596\u2013615 (1987)","journal-title":"Journal of the ACM"},{"issue":"2","key":"7_CR12","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate Distance Oracles Revisited. In: Proc. 13th International Symposium on Algorithms and Computation, pp. 357\u2013368 (2002)","DOI":"10.1007\/3-540-36136-7_32"},{"key":"7_CR14","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate Distance Oracles for Geometric Spanners. Submitted August 2004. \u00a0hgudmund\/glns-adogs-04.pdf. Extended abstract published in Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 828-837 (2002), http:\/\/win.tue.nl\/"},{"key":"7_CR15","unstructured":"Gudmundsson, J., Narasimhan, G., Smid, M.: Fast Pruning of Geometric Spanners. Submitted \u00a0hgudmund\/gns-fps-04.pdf (June 2004), http:\/\/win.tue.nl\/"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Krznaric, D., Levcopoulos, C.: Computing hierarchies of clusters from the Euclidean minimum spanning tree in linear time. In: Proc. 15th Conf. on Foundations of Software Technology and Theoretical Computer Science, pp. 443-455 (1995)","DOI":"10.1007\/3-540-60692-0_66"},{"key":"7_CR17","first-page":"445","volume-title":"Handbook of Discrete and Computational Geometry","author":"J.S.B. Mitchell","year":"1997","unstructured":"Mitchell, J.S.B.: Shortest paths and networks. In: Handbook of Discrete and Computational Geometry, pp. 445\u2013466. CRC Press LLC, Boca Raton (1997)"},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1145\/261342.261352","volume":"28","author":"R. Raman","year":"1997","unstructured":"Raman, R.: Recent results on the single-source shortest paths problem. SIGACT News\u00a028, 81\u201387 (1997)","journal-title":"SIGACT News"},{"issue":"5","key":"7_CR19","doi-asserted-by":"publisher","first-page":"982","DOI":"10.1145\/185675.185795","volume":"41","author":"J.A. Storer","year":"1994","unstructured":"Storer, J.A., Reif, J.H.: Shortest Paths in the Plane with Polygonal Obstacles. Journal of the ACM\u00a041(5), 982\u20131012 (1994)","journal-title":"Journal of the ACM"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In: Proc. 33rd ACM Symposium on Theory of Computing, pp. 183\u2013192 (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\/978-3-540-30551-4_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:21:32Z","timestamp":1605741692000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30551-4_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241317","9783540305514"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30551-4_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}