{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:27:47Z","timestamp":1778495267075,"version":"3.51.4"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2010,12,24]],"date-time":"2010-12-24T00:00:00Z","timestamp":1293148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,4]]},"DOI":"10.1007\/s00453-010-9478-x","type":"journal-article","created":{"date-parts":[[2010,12,23]],"date-time":"2010-12-23T19:24:51Z","timestamp":1293132291000},"page":"713-732","source":"Crossref","is-referenced-by-count":36,"title":["Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs"],"prefix":"10.1007","volume":"62","author":[{"given":"Victor","family":"Chepoi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feodor F.","family":"Dragan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bertrand","family":"Estellon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"Habib","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yann","family":"Vax\u00e8s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Xiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,12,24]]},"reference":[{"key":"9478_CR1","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1145\/1146381.1146411","volume-title":"Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing (PODC 2006)","author":"I. Abraham","year":"2006","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing (PODC 2006), Denver, Colorado, USA, 23\u201326 July 2006, pp.\u00a0188\u2013197. ACM, New York (2006)"},{"key":"9478_CR2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/ICDCS.2006.72","volume-title":"Proceedings of 26th International Conference on Distributed Computing Systems (ICDCS 2006)","author":"I. Abraham","year":"2006","unstructured":"Abraham, I., Gavoille, C., Goldberg, A.V., Malkhi, D.: Routing in networks with low doubling dimension. In: Proceedings of 26th International Conference on Distributed Computing Systems (ICDCS 2006), p.\u00a075. IEEE Comput. Soc., Los Alamitos (2006)"},{"key":"9478_CR3","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1281100.1281110","volume-title":"Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC 2007)","author":"I. Abraham","year":"2007","unstructured":"Abraham, I., Balakrishnan, M., Kuhn, F., Malkhi, D., Ramasubramanian, V., Talwar, K.: Reconstructing approximate tree metrics. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC 2007), Portland, Oregon, USA, 12\u201315 August 2007, pp.\u00a043\u201352. ACM, New York (2007)"},{"key":"9478_CR4","first-page":"3","volume-title":"Group Theory from a Geometrical Viewpoint, ICTP Trieste 1990","author":"J.M. Alonso","year":"1991","unstructured":"Alonso, J.M., Brady, T., Cooper, D., Ferlini, V., Lustig, M., Mihalik, M., Shapiro, M., Short, H.: Notes on word hyperbolic groups. In: Ghys, E., Haefliger, A., Verjovsky, A. (eds.) Group Theory from a Geometrical Viewpoint, ICTP Trieste 1990, pp.\u00a03\u201363. World Scientific, Singapore (1991),"},{"key":"9478_CR5","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1137\/S0895480103433409","volume":"19","author":"S. Alstrup","year":"2005","unstructured":"Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. SIAM J. Discrete Math. 19, 448\u2013462 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"9478_CR6","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s10711-006-9102-z","volume":"121","author":"V. Alvarez","year":"2006","unstructured":"Alvarez, V., Portilla, A., Rodriguez, J.M., Touris, E.: Gromov hyperbolicity of Denjoy domains. Geom. Dedic. 121, 221\u2013245 (2006)","journal-title":"Geom. Dedic."},{"key":"9478_CR7","first-page":"512","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)","author":"M. B\u01cedoiu","year":"2007","unstructured":"B\u01cedoiu, M., Indyk, P., Sidiropoulos, A.: Approximation algorithms for embedding general metrics into trees. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, USA, 7\u20139 January 2007, pp.\u00a0512\u2013521. SIAM, Philadelphia (2007)"},{"key":"9478_CR8","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/S0895480100380902","volume":"16","author":"H.-J. Bandelt","year":"2003","unstructured":"Bandelt, H.-J., Chepoi, V.: 1-Hyperbolic graphs. SIAM J. Discrete Math. 16, 323\u2013334 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"9478_CR9","doi-asserted-by":"crossref","first-page":"3465","DOI":"10.1016\/j.disc.2007.12.091","volume":"309","author":"F. Bazzaro","year":"2009","unstructured":"Bazzaro, F., Gavoille, C.: Localized and compact data-structure for comparability graphs. Discrete Math. 309, 3465\u20133484 (2009)","journal-title":"Discrete Math."},{"key":"9478_CR10","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1006\/jagm.1998.0962","volume":"30","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Chepoi, V., Dragan, F.: Distance approximating trees for chordal and dually chordal graphs. J. Algorithms 30, 166\u2013184 (1999)","journal-title":"J. Algorithms"},{"key":"9478_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-12494-9","volume-title":"Metric Spaces of Non-Positive Curvature","author":"M. Bridson","year":"1999","unstructured":"Bridson, M., Haefliger, A.: Metric Spaces of Non-Positive Curvature. Springer, Berlin (1999)"},{"key":"9478_CR12","first-page":"762","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)","author":"H.T.-H. Chan","year":"2005","unstructured":"Chan, H.T.-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, 23\u201325 January 2005, pp.\u00a0762\u2013771. SIAM, Philadelphia (2005)"},{"key":"9478_CR13","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1006\/eujc.1999.0381","volume":"21","author":"V. Chepoi","year":"2000","unstructured":"Chepoi, V., Dragan, F.: A note on distance approximating trees in graphs. Eur. J. Comb. 21, 761\u2013766 (2000)","journal-title":"Eur. J. Comb."},{"key":"9478_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/978-3-540-74208-1_5","volume-title":"Proceedings of Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007","author":"V. Chepoi","year":"2007","unstructured":"Chepoi, V., Estellon, B.: Packing and covering \u03b4-hyperbolic spaces by balls. In: Proceedings of Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, 20\u201322 August 2007. Lecture Notes in Computer Science, vol.\u00a04627, pp.\u00a059\u201373. Springer, Berlin (2007)"},{"key":"9478_CR15","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.tcs.2005.05.017","volume":"347","author":"V. Chepoi","year":"2005","unstructured":"Chepoi, V., Dragan, F.F., Yan, C.: Additive sparse spanners for graphs with bounded length of largest induced cycle. Theor. Comput. Sci. 347, 54\u201375 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9478_CR16","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.jalgor.2004.07.011","volume":"61","author":"V. Chepoi","year":"2006","unstructured":"Chepoi, V., Dragan, F., Vax\u00e8s, Y.: Distance and routing labeling schemes for non-positively curved plane graphs. J. Algorithms 61, 60\u201388 (2006)","journal-title":"J. Algorithms"},{"key":"9478_CR17","first-page":"59","volume-title":"Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008)","author":"V. Chepoi","year":"2008","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Diameters, centers, and approximating trees of \u03b4-hyperbolic geodesic spaces and graphs. In: Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008), 9\u201311 June 2008, College Park, Maryland, USA, pp.\u00a059\u201368 (2008)"},{"key":"9478_CR18","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/S0166-218X(02)00421-3","volume":"131","author":"B. Courcelle","year":"2003","unstructured":"Courcelle, B., Vanicat, R.: Query efficient implementation of graphs of bounded clique-width. Discrete Appl. Math. 131, 129\u2013150 (2003)","journal-title":"Discrete Appl. Math."},{"key":"9478_CR19","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"38","author":"L. Cowen","year":"2001","unstructured":"Cowen, L.: Compact Routing with Minimum Stretch. J. Algorithms 38, 170\u2013183 (2001)","journal-title":"J. Algorithms"},{"key":"9478_CR20","doi-asserted-by":"crossref","first-page":"277","DOI":"10.7155\/jgaa.00109","volume":"9","author":"Y. Dourisboure","year":"2005","unstructured":"Dourisboure, Y.: Compact routing schemes for generalised chordal graphs. J. Graph Algorithms Appl. 9, 277\u2013297 (2005)","journal-title":"J. Graph Algorithms Appl."},{"key":"9478_CR21","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/j.disc.2005.12.060","volume":"307","author":"Y. Dourisboure","year":"2007","unstructured":"Dourisboure, Y., Gavoille, C.: Tree-decompositions with bags of small diameter. Discrete Math. 307, 208\u2013229 (2007)","journal-title":"Discrete Math."},{"key":"9478_CR22","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.tcs.2007.03.058","volume":"383","author":"Y. Dourisboure","year":"2007","unstructured":"Dourisboure, Y., Dragan, F.F., Gavoille, C., Yan, C.: Spanners for bounded tree-length graphs. Theor. Comput. Sci. 383, 34\u201344 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9478_CR23","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1007\/s00453-008-9194-y","volume":"57","author":"F.F. Dragan","year":"2010","unstructured":"Dragan, F.F., Yan, C.: Collective tree spanners in graphs with bounded parameters. Algorithmica 57, 22\u201343 (2010)","journal-title":"Algorithmica"},{"key":"9478_CR24","doi-asserted-by":"crossref","first-page":"97","DOI":"10.7155\/jgaa.00120","volume":"10","author":"F.F. Dragan","year":"2006","unstructured":"Dragan, F.F., Yan, C., Corneil, D.G.: Collective tree spanners and routing in AT-free related graphs. J.\u00a0Graph Algorithms Appl. 10, 97\u2013122 (2006)","journal-title":"J.\u00a0Graph Algorithms Appl."},{"key":"9478_CR25","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1137\/S089548010444167X","volume":"20","author":"F.F. Dragan","year":"2006","unstructured":"Dragan, F.F., Yan, C., Lomonosov, I.: Collective tree spanners of graphs. SIAM J. Discrete Math. 20, 241\u2013260 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"9478_CR26","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0196-6774(03)00002-6","volume":"46","author":"T. Eilam","year":"2003","unstructured":"Eilam, T., Gavoille, C., Peleg, D.: Compact routing schemes with low stretch factor. J. Algorithms 46, 97\u2013114 (2003)","journal-title":"J. Algorithms"},{"key":"9478_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1007\/3-540-48224-5_62","volume-title":"Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 2001)","author":"P. Fraigniaud","year":"2001","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in trees. In: Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 2001), Crete, Greece, 8\u201312 July 2001. Lecture Notes in Computer Science, vol.\u00a02076, pp.\u00a0757\u2013772. Springer, Berlin (2001)"},{"key":"9478_CR28","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1006\/jpdc.2000.1705","volume":"61","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C., Gengler, M.: Space-efficiency of routing schemes of stretch factor three. J. Parallel Distrib. Comput. 61, 679\u2013687 (2001)","journal-title":"J. Parallel Distrib. Comput."},{"key":"9478_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/3-540-48523-6_32","volume-title":"Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP\u201999)","author":"C. Gavoille","year":"1999","unstructured":"Gavoille, C., Hanusse, N.: Compact routing tables for graphs of bounded genus. In: Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP\u201999), Prague, Czech Republic, 11\u201315 July 1999. Lecture Notes in Computer Science, vol.\u00a01644, pp.\u00a0351\u2013360. Springer, Berlin (1999)"},{"key":"9478_CR30","series-title":"Lecture Notes in Computer Science","first-page":"171","volume-title":"Proceedings of 16th International Symposium on Algorithms and Computation (ISAAC 2005)","author":"C. Gavoille","year":"2005","unstructured":"Gavoille, C., Ly, O.: Distance labeling in hyperbolic graphs. In: Proceedings of 16th International Symposium on Algorithms and Computation (ISAAC 2005), Sanya, Hainan, China, 19\u201321 December 2005. Lecture Notes in Computer Science, vol.\u00a03827, pp.\u00a0171\u2013179. Springer, Berlin (2005)"},{"key":"9478_CR31","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/S0012-365X(03)00232-2","volume":"273","author":"C. Gavoille","year":"2003","unstructured":"Gavoille, C., Paul, C.: Distance labeling scheme and split decomposition. Discrete Math. 273, 115\u2013130 (2003)","journal-title":"Discrete Math."},{"key":"9478_CR32","doi-asserted-by":"crossref","first-page":"1239","DOI":"10.1137\/050635006","volume":"22","author":"C. Gavoille","year":"2008","unstructured":"Gavoille, C., Paul, C.: Optimal distance labeling for interval graphs and related graph families. SIAM J. Discrete Math. 22, 1239\u20131258 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"9478_CR33","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s00446-002-0073-5","volume":"16","author":"C. Gavoille","year":"2003","unstructured":"Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distrib. Comput. 16, 111\u2013120 (2003)","journal-title":"Distrib. Comput."},{"key":"9478_CR34","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1145\/248052.248075","volume-title":"Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing (PODC 1996)","author":"C. Gavoille","year":"1996","unstructured":"Gavoille, C., P\u00e9renn\u00e8s, S.: Memory requirements for routing in distributed networks. In: Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing (PODC 1996), Philadelphia, Pennsylvania, USA, 23\u201326 May 1996, pp.\u00a0125\u2013133. ACM, New York (1996)"},{"key":"9478_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1007\/3-540-44676-1_40","volume-title":"Proceedings of the 9th Annual European Symposium on Algorithms (ESA 2001)","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: Approximate distance labeling schemes. In: Proceedings of the 9th Annual European Symposium on Algorithms (ESA 2001), Aarhus, Denmark, 28\u201331 August 2001. Lecture Notes in Computer Science, vol.\u00a02161, pp.\u00a0476\u2013488. Springer, Berlin (2001)"},{"key":"9478_CR36","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C. Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9renn\u00e8s, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53, 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"9478_CR37","series-title":"Progress in Mathematics","volume-title":"Les Groupes Hyperboliques d\u2019Apr\u00e8s M. Gromov","year":"1990","unstructured":"Ghys, E., de\u00a0la Harpe, P. (eds.): Les Groupes Hyperboliques d\u2019Apr\u00e8s M. Gromov. Progress in Mathematics, vol.\u00a083. Birkh\u00e4user, Basel (1990)"},{"key":"9478_CR38","series-title":"MSRI Series","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-1-4613-9586-7_3","volume-title":"Essays in Group Theory","author":"M. Gromov","year":"1987","unstructured":"Gromov, M.: Hyperbolic Groups. In: Gersten, S.M. (ed.) Essays in Group Theory. MSRI Series, vol.\u00a08, pp.\u00a075\u2013263 (1987)"},{"key":"9478_CR39","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1109\/SFCS.2003.1238226","volume-title":"Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003)","author":"A. Gupta","year":"2003","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), Cambridge, MA, USA, 11\u201314 October 2003, pp.\u00a0534\u2013543. IEEE Comput. Soc., Los Alamitos (2003)"},{"key":"9478_CR40","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1137\/S0097539702409927","volume":"34","author":"A. Gupta","year":"2005","unstructured":"Gupta, A., Kumar, A., Rastogi, R.: Traveling with a pez dispenser (or, routing issues in mpls). SIAM J. Comput. 34, 453\u2013474 (2005)","journal-title":"SIAM J. Comput."},{"key":"9478_CR41","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S. Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low dimensional metrics, and their applications, fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35, 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"key":"9478_CR42","first-page":"73","volume":"48","author":"A. Karlsson","year":"2002","unstructured":"Karlsson, A., Noskov, G.: The Hilbert metric and Gromov hyperbolicity. Enseign. Math. 48, 73\u201389 (2002)","journal-title":"Enseign. Math."},{"key":"9478_CR43","first-page":"682","volume-title":"Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC 1993)","author":"P. Klein","year":"1993","unstructured":"Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC 1993), pp.\u00a0682\u2013690. ACM, New York (1993)"},{"key":"9478_CR44","doi-asserted-by":"crossref","first-page":"1902","DOI":"10.1109\/INFCOM.2007.221","volume-title":"Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM 2007)","author":"R. Kleinberg","year":"2007","unstructured":"Kleinberg, R.: Geographic routing using hyperbolic space. In: Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM 2007), Anchorage, Alaska, USA, 6\u201312 May 2007, pp.\u00a01902\u20131909. IEEE Press, New York (2007)"},{"key":"9478_CR45","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1145\/1146381.1146412","volume-title":"Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC 2006)","author":"G. Konjevod","year":"2006","unstructured":"Konjevod, G., Richa, A.W., Xia, D.: Optimal-stretch name-independent compact routing in doubling metrics. In: Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC 2006), Denver, CO, USA, 23\u201326 July 2006, pp.\u00a0198\u2013207. ACM, New York (2006)"},{"key":"9478_CR46","first-page":"939","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)","author":"G. Konjevod","year":"2007","unstructured":"Konjevod, G., Richa, A.W., Xia, D.: Optimal scale-free compact routing schemes in networks of low doubling dimension. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, USA, 7\u20139 January 2007, pp.\u00a0939\u2013948. SIAM, Philadelphia (2007)"},{"key":"9478_CR47","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1145\/1281100.1281113","volume-title":"Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing (PODC 2007)","author":"G. Konjevod","year":"2007","unstructured":"Konjevod, G., Richa, A., Xia, D., Yu, H.: Compact routing with slack in low doubling dimension. In: Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing (PODC 2007), Portland, Oregon, USA, 12\u201315 August 2007, pp.\u00a071\u201380. ACM, New York (2007)"},{"key":"9478_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/978-3-540-87779-0_26","volume-title":"Proceedings of the 22nd International Symposium on Distributed Computing (DISC 2008)","author":"G. Konjevod","year":"2008","unstructured":"Konjevod, G., Richa, A.W., Xia, D.: Dynamic routing and location services in metrics of low doubling dimension. In: Proceedings of the 22nd International Symposium on Distributed Computing (DISC 2008), Arcachon, France, 22\u201324 September 2008, Lecture Notes in Computer Science, vol.\u00a05218, pp.\u00a0379\u2013393. Springer, Berlin (2008)"},{"key":"9478_CR49","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1006\/eujc.2002.0591","volume":"23","author":"J. Koolen","year":"2002","unstructured":"Koolen, J., Moulton, V.: Hyperbolic bridged graphs. Eur. J. Comb. 23, 683\u2013699 (2002)","journal-title":"Eur. J. Comb."},{"key":"9478_CR50","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1109\/FOCS.2006.9","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006)","author":"R. Krauthgamer","year":"2006","unstructured":"Krauthgamer, R., Lee, J.R.: Algorithms on negatively curved spaces. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), Berkeley, California, USA, 21\u201324 October 2006, pp.\u00a0119\u2013132. IEEE Comput. Soc., Los Alamitos (2006)"},{"key":"9478_CR51","series-title":"SIAM Monographs on Discrete Math. Appl.","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Math. Appl. SIAM, Philadelphia (2000)"},{"key":"9478_CR52","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5","volume":"33","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Proximity-preserving labeling schemes and their applications. J. Graph Theory 33, 167\u2013176 (2000)","journal-title":"J. Graph Theory"},{"key":"9478_CR53","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1109\/TNET.2007.899021","volume":"16","author":"Y. Shavitt","year":"2008","unstructured":"Shavitt, Y., Tankel, T.: Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE\/ACM Trans. Netw. 16, 25\u201336 (2008)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"9478_CR54","first-page":"640","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)","author":"A. Slivkins","year":"2005","unstructured":"Slivkins, A.: Distributed approaches to triangulation and embedding. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, 23\u201325 January 2005, pp.\u00a0640\u2013649. SIAM, New York (2005)"},{"key":"9478_CR55","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/s00446-006-0015-8","volume":"19","author":"A. Slivkins","year":"2007","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. Distrib. Comput. 19, 313\u2013333 (2007)","journal-title":"Distrib. Comput."},{"key":"9478_CR56","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1145\/1007352.1007399","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004)","author":"K. Talwar","year":"2004","unstructured":"Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), Chicago, IL, USA, 13\u201316 June 2004, pp.\u00a0281\u2013290. ACM, New York (2004)"},{"key":"9478_CR57","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. Assoc. Comput. Mach. 51, 993\u20131024 (2004)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9478_CR58","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/378580.378581","volume-title":"Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001)","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001), Heraklion, Crete, Greece, 4\u20136 July 2001, pp.\u00a01\u201310. ACM, New York (2001)"},{"key":"9478_CR59","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. Assoc. Comput. Mach. 52, 1\u201324 (2005)","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9478-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9478-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9478-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:07Z","timestamp":1559137507000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9478-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,24]]},"references-count":59,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9478"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9478-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12,24]]}}}