{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T05:06:58Z","timestamp":1736485618636,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540343752"},{"type":"electronic","value":"9783540343783"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11758471_26","type":"book-chapter","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T10:34:15Z","timestamp":1149244455000},"page":"260-271","source":"Crossref","is-referenced-by-count":1,"title":["Distance Approximating Trees: Complexity and Algorithms"],"prefix":"10.1007","author":[{"given":"Feodor F.","family":"Dragan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenyu","family":"Yan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabalistic approximation of metric spaces and its algorithmic applications. In: FOCS 1996, pp. 184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Blum, A., Burch, C., Tomkins, A.: A polylog(n)competitive algorithm for metrical task systems. In: STOC 1997, pp. 711\u2013719 (1997)","DOI":"10.1145\/258533.258667"},{"key":"26_CR3","volume-title":"Trees and Proximity Representations","author":"J.-P. Barth\u00e9lemy","year":"1991","unstructured":"Barth\u00e9lemy, J.-P., Gu\u00e9noche, A.: Trees and Proximity Representations. Wiley, New York (1991)"},{"key":"26_CR4","doi-asserted-by":"publisher","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.F.: Distance Approximating Trees for Chordal and Dually Chordal Graphs. Journal of Algorithms\u00a030, 166\u2013184 (1999)","journal-title":"Journal of Algorithms"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/S0304-3975(03)00424-9","volume":"310","author":"A. Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A., Dragan, F., Le, H.-O., Le, V.B.: Tree Spanners on Chordal Graphs: Complexity and Algorithms. Theor. Comput. Science\u00a0310, 329\u2013354 (2004)","journal-title":"Theor. Comput. Science"},{"key":"26_CR6","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L. Cai","year":"1995","unstructured":"Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Disc. Math.\u00a08, 359\u2013387 (1995)","journal-title":"SIAM J. Disc. Math."},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.: Approximating a Finite Metric by a Small Number of Tree Metrics. In: FOCS 1998, pp. 379\u2013388 (1998)","DOI":"10.1109\/SFCS.1998.743488"},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1006\/eujc.1999.0381","volume":"21","author":"V. Chepoi","year":"2000","unstructured":"Chepoi, V., Dragan, F.F.: A note on distance approximating trees in graphs. European Journal of Combinatorics\u00a021, 761\u2013766 (2000)","journal-title":"European Journal of Combinatorics"},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"L.P. Chew","year":"1989","unstructured":"Chew, L.P.: There are planar graphs almost as good as the complete graph. J. of Computer and System Sciences\u00a039, 205\u2013219 (1989)","journal-title":"J. of Computer and System Sciences"},{"key":"26_CR10","unstructured":"Emek, Y., Peleg, D.: Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs. In: SODA 2004, pp. 261\u2013270 (2004)"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: STOC 2003, pp. 448\u2013455 (2003)","DOI":"10.1145\/780542.780608"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1006\/jcss.1999.1682","volume":"60","author":"U. Feige","year":"2000","unstructured":"Feige, U.: Approximating the Bandwidth via Volume Respecting Embeddings. J. Comput. System Sci.\u00a060, 510\u2013539 (2000)","journal-title":"J. Comput. System Sci."},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jagm.2000.1118","volume":"40","author":"A. Gupta","year":"2001","unstructured":"Gupta, A.: Improved bandwidth approximation for trees and chordal graphs. Journal of Algorithms\u00a040, 24\u201336 (2001)","journal-title":"Journal of Algorithms"},{"key":"26_CR14","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput.\u00a02, 135\u2013158 (1973)","journal-title":"SIAM J. Comput."},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0137040","volume":"37","author":"O. Kariv","year":"1979","unstructured":"Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems, I: the p-centers. SIAM J. Appl. Math.\u00a037, 513\u2013538 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"26_CR16","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1137\/S0895480195295471","volume":"17","author":"D. Kratsch","year":"2003","unstructured":"Kratsch, D., Le, H.-O., M\u00fcller, H., Prisner, E., Wagner, D.: Additive tree spanners. SIAM J. Discrete Math.\u00a017, 332\u2013340 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Lee, J.R.: The intrinsic dimensionality of graphs. In: STOC 2003, pp. 438\u2013447 (2003)","DOI":"10.1145\/780542.780607"},{"key":"26_CR18","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s00454-003-2872-2","volume":"31","author":"R. Krauthgamer","year":"2004","unstructured":"Krauthgamer, R., Linial, N., Magen, A.: Metric Embedding \u2013 Beyond one-dimensional distortion. Discrete and Computational Geometry\u00a031, 339\u2013356 (2004)","journal-title":"Discrete and Computational Geometry"},{"key":"26_CR19","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/net.3230230417","volume":"23","author":"A.L. Liestman","year":"1993","unstructured":"Liestman, A.L., Shermer, T.: Additive graph spanners. Networks\u00a023, 343\u2013364 (1993)","journal-title":"Networks"},{"key":"26_CR20","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some its algorithmic applications. Combinatorica\u00a015, 215\u2013245 (1995)","journal-title":"Combinatorica"},{"key":"26_CR21","unstructured":"McKee, T.A.: Personal communication to E. Prisner (1995)"},{"key":"26_CR22","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01191205","volume":"12","author":"G.L. Miller","year":"1992","unstructured":"Miller, G.L., Ramachandran, V.: A new graph triconnectivity algorithm and its parallelization. Combinatorica\u00a012, 53\u201376 (1992)","journal-title":"Combinatorica"},{"key":"26_CR23","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph Spanners. J. Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"key":"26_CR24","doi-asserted-by":"crossref","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. In: PODC 1987, pp. 77\u201385 (1987)","DOI":"10.1145\/41840.41847"},{"key":"26_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/BFb0023484","volume-title":"STACS 97","author":"E. Prisner","year":"1997","unstructured":"Prisner, E.: Distance approximating spanning trees. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol.\u00a01200, pp. 499\u2013510. Springer, Heidelberg (1997)"},{"key":"26_CR26","volume-title":"Numerical Taxonomy","author":"P.H.A. Sneath","year":"1973","unstructured":"Sneath, P.H.A., Sokal, R.R.: Numerical Taxonomy. W.H. Freeman, San Francisco (1973)"},{"key":"26_CR27","first-page":"411","volume-title":"Molecular Systematics","author":"D.L. Swofford","year":"1990","unstructured":"Swofford, D.L., Olsen, G.J.: Phylogeny reconstruction. In: Hillis, D.M., Moritz, C. (eds.) Molecular Systematics, pp. 411\u2013501. Sinauer Associates Inc., Sunderland (1990)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11758471_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T05:17:07Z","timestamp":1736399827000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11758471_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540343752","9783540343783"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/11758471_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}