{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T10:42:01Z","timestamp":1789641721741,"version":"4.0.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642153686","type":"print"},{"value":"9783642153693","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_8","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"95-109","source":"Crossref","is-referenced-by-count":2,"title":["Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs"],"prefix":"10.1007","author":[{"given":"Victor","family":"Chepoi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Feodor F.","family":"Dragan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuri","family":"Rabinovich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yann","family":"Vax\u00e8s","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","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.\u00a028 (1999)","DOI":"10.1137\/S0097539795296334"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Chuzhoy, J., Indyk, P., Sidiropoulos, A.: Low-distortion embeddings of general metrics into the line. In: STOC 2005 (2005)","DOI":"10.1145\/1060590.1060624"},{"key":"8_CR3","unstructured":"B\u01cedoiu, M., Demaine, E.D., Hajiaghayi, M.T., Sidiropoulos, A., Zadimoghaddam, M.: Ordinal embedding: approximation algorithms and dimensionality reduction. In: APPROX-RANDOM 2008 (2008)"},{"key":"8_CR4","unstructured":"B\u01cedoiu, M., Indyk, P., Sidiropoulos, A.: Approximation algorithms for embedding general metrics into trees. In: SODA 2007 (2007)"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Chepoi, V., Dragan, F.: Distance approximating trees for chordal and dually chordal graphs. J. Algorithms\u00a030 (1999)","DOI":"10.1006\/jagm.1998.0962"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F.: A note on distance approximating trees in graphs. Europ. J. Combin. 21 (2000)","DOI":"10.1006\/eujc.1999.0381"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Diameters, centers, and approximating trees of \u03b4-hyperbolic geodesic spaces and graphs. In: SoCG 2008 (2008)","DOI":"10.1016\/j.endm.2008.06.046"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Fichet, B.: l \u2009\u221e\u2009-Approximation via subdominants. J. Math. Psychol.\u00a044 (2000)","DOI":"10.1006\/jmps.1999.1270"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Dourisboure, Y., Dragan, F.F., Gavoille, C., Yan, C.: Spanners for bounded tree-length graphs. Theor. Comput. Sci.\u00a0383 (2007)","DOI":"10.1016\/j.tcs.2007.03.058"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Dourisboure, Y., Gavoille, C.: Tree-decompositions with bags of small diameter. Discr. Math.\u00a0307 (2007)","DOI":"10.1016\/j.disc.2005.12.060"},{"key":"8_CR11","unstructured":"Emek, Y., Peleg, D.: Approximating minimum max-stretch spanning trees on unweighted graphs. In: SODA 2004 (2004)"},{"key":"8_CR12","unstructured":"Gupta, A.: Steiner points in tree metrics don\u2019t (really) help. In: SODA 2001 (2001)"},{"key":"8_CR13","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: Handbook of Discrete and Computational Geometry. CRC Press, LLC (2004)"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Lee, J.R.: Algorithms on negatively curved spaces. In: FOCS 2006 (2006)","DOI":"10.1109\/FOCS.2006.9"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Rabinovich, Y., Raz, R.: Lower bounds on the distortion of embedding finite metric spaces in graphs. Discr. Comput. Geom.\u00a019 (1998)","DOI":"10.1007\/PL00009336"},{"key":"8_CR16","unstructured":"Shavitt, Y., Tankel, T.: On internet embedding in hyperbolic spaces for overlay construction and distance estimation. In: INFOCOM 2004 (2004)"},{"key":"8_CR17","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, Oxford (2003)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,29]],"date-time":"2024-03-29T22:27:49Z","timestamp":1711751269000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}