{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:35:39Z","timestamp":1767339339099},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,11,23]],"date-time":"2011-11-23T00:00:00Z","timestamp":1322006400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2012,1]]},"DOI":"10.1007\/s00454-011-9386-0","type":"journal-article","created":{"date-parts":[[2011,11,22]],"date-time":"2011-11-22T16:27:35Z","timestamp":1321979255000},"page":"187-214","source":"Crossref","is-referenced-by-count":10,"title":["Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs"],"prefix":"10.1007","volume":"47","author":[{"given":"V.","family":"Chepoi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F. F.","family":"Dragan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I.","family":"Newman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"Rabinovich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"Vax\u00e8s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,11,23]]},"reference":[{"key":"9386_CR1","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/S0097539795296334","volume":"28","author":"R. Agarwala","year":"1999","unstructured":"Agarwala, R., Bafna, V., Farach, M., Narayanan, B., Paterson, M., Thorup, M.: On the approximability of numerical taxonomy (fitting distances by tree metrics). SIAM J. Comput. 28, 1073\u20131085 (1999)","journal-title":"SIAM J. Comput."},{"key":"9386_CR2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/1060590.1060624","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005)","author":"M. B\u0103doiu","year":"2005","unstructured":"B\u0103doiu, M., Chuzhoy, J., Indyk, P., Sidiropoulos, A.: Low-distortion embeddings of general metrics into the line. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005) Baltimore, MD, USA, May 22\u201324, pp. 225\u2013233. ACM, New York (2005)"},{"key":"9386_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/978-3-540-85363-3_3","volume-title":"Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008)","author":"M. B\u01cedoiu","year":"2008","unstructured":"B\u01cedoiu, M., Demaine, E.D., Hajiaghayi, M.T., Sidiropoulos, A., Zadimoghaddam, M.: Ordinal embedding: approximation algorithms and dimensionality reduction. In: Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008), Boston, MA, USA, August 25\u201327. Lecture Notes in Computer Science, vol. 5171, pp. 21\u201334. Springer, Berlin (2008)"},{"key":"9386_CR4","first-page":"512","volume-title":"Proceedings of the Eighteenth Annual ACM\u2013SIAM 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\u2013SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, USA, January 7\u20139, pp. 512\u2013521. ACM\/SIAM, New York (2007)"},{"key":"9386_CR5","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":"9386_CR6","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":"9386_CR7","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), June 9\u201311, College Park, Maryland, USA, pp. 59\u201368. ACM, New York (2008)"},{"key":"9386_CR8","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1006\/jmps.1999.1270","volume":"44","author":"V. Chepoi","year":"2000","unstructured":"Chepoi, V., Fichet, B.: l \u221e-Approximation via subdominants. J. Math. Psychol. 44, 600\u2013616 (2000)","journal-title":"J. Math. Psychol."},{"key":"9386_CR9","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Springer, Berlin (2005)"},{"key":"9386_CR10","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":"9386_CR11","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":"9386_CR12","doi-asserted-by":"crossref","first-page":"1761","DOI":"10.1137\/060666202","volume":"38","author":"Y. Emek","year":"2008","unstructured":"Emek, Y., Peleg, D.: Approximating minimum max-stretch spanning trees on unweighted graphs. SIAM J. Comput. 38, 1761\u20131781 (2008)","journal-title":"SIAM J. Comput."},{"key":"9386_CR13","first-page":"220","volume-title":"Proceedings of the Twelfth Annual Symposium on Discrete Algorithms (SODA 2001)","author":"A. Gupta","year":"2001","unstructured":"Gupta, A.: Steiner points in tree metrics don\u2019t (really) help. In: Proceedings of the Twelfth Annual Symposium on Discrete Algorithms (SODA 2001), January 7\u20139, Washington, DC, USA, pp. 220\u2013227. ACM\/SIAM, New York (2001)"},{"key":"9386_CR14","first-page":"177","volume-title":"Handbook of Discrete and Computational Geometry","author":"P. Indyk","year":"2004","unstructured":"Indyk, P., Matousek, J.: Low-distortion embeddings of finite metric spaces. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 177\u2013196. CRC Press, Boca Raton (2004)","edition":"2"},{"key":"9386_CR15","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), 21\u201324 October 2006, Berkeley, California, USA, pp. 119\u2013132. IEEE, New York (2006)"},{"key":"9386_CR16","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/PL00009336","volume":"19","author":"Y. Rabinovich","year":"1998","unstructured":"Rabinovich, Y., Raz, R.: Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete Comput. Geom. 19, 79\u201394 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"9386_CR17","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":"9386_CR18","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C. Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford University Press, London (2003)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-011-9386-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-011-9386-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-011-9386-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,14]],"date-time":"2024-04-14T23:21:39Z","timestamp":1713136899000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-011-9386-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,23]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["9386"],"URL":"https:\/\/doi.org\/10.1007\/s00454-011-9386-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,23]]}}}