{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T17:01:33Z","timestamp":1780074093767,"version":"3.54.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540006237","type":"print"},{"value":"9783540364948","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36494-3_32","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T21:12:04Z","timestamp":1269897124000},"page":"355-366","source":"Crossref","is-referenced-by-count":10,"title":["Representing Graph Metrics with Fewest Edges"],"prefix":"10.1007","author":[{"given":"T.","family":"Feder","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A.","family":"Meyerson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Motwani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L.","family":"O\u2019Callaghan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Panigrahy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2003,2,17]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"I. Althofer. \u201cOn optimal realizations of finite metric spaces by graphs.\u201d Discrete Comp. Geom 3, 1988.","DOI":"10.1007\/BF02187901"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"S. Arya, G. Das, D. M. Mount, J. S. Salowe, and M. H. M. Smid. \u201cEuclidean spanners: short, thin, and lanky.\u201d In Proc. STOC, 1995.","DOI":"10.1145\/225058.225191"},{"key":"32_CR3","unstructured":"Y. Bartal. \u201cProbabilistic approximation of metric spaces and its algorithmic applications.\u201d In Proc FOCS, 1996."},{"key":"32_CR4","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1090\/qam\/265210","volume":"26","author":"F. Boesch","year":"1968\u201369","unstructured":"F. Boesch. \u201cProperties of the distance matrix of a tree.\u201d Quart. Appl. Math. 26 (1968\u201369), 607\u2013609.","journal-title":"Quart. Appl. Math"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin. \u201cApproximating a finite metric by a small number of tree metrics.\u201d In Proc. FOCS, 1998.","DOI":"10.1109\/SFCS.1998.743488"},{"key":"32_CR6","unstructured":"F. Chung, M. Garrett, R. Graham, and D. Shallcross. \u201cDistance realization problems with applications to internet tomography.\u201d Preprint, http:\/\/www.math.ucsd.edu\/~fan ."},{"key":"32_CR7","unstructured":"G. Das, G. Narasimhan, and J. Salowe. \u201cA new way to weigh malnourished Euclidean graphs.\u201d In Proc. SODA, 1995."},{"key":"32_CR8","unstructured":"I. Dinur and M. Safra. Personal communication."},{"key":"32_CR9","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0001-8708(84)90029-X","volume":"53","author":"A. W. M. Dress","year":"1984","unstructured":"A. W. M. Dress. \u201cTrees, tight extensions of metric spaces, and the cohomological dimension of certain groups.\u201d Advances in Mathematics 53 (1984), 321\u2013402.","journal-title":"Advances in Mathematics"},{"key":"32_CR10","first-page":"261","volume":"51","author":"T. Feder","year":"1995","unstructured":"T. Feder and R. Motwani. \u201cClique compressions, graph partitions and speeding-up algorithms.\u201d JCSS 51 (1995), 261\u2013272.","journal-title":"JCSS"},{"key":"32_CR11","unstructured":"U. Feige and J. Kilian. \u201cZero-knowledge and chromatic number.\u201d In Proc. Annual Conf. on Comp. Complex. (1996)."},{"key":"32_CR12","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G. Gallo","year":"1989","unstructured":"G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. \u201cA fast parametric maximum flow algorithm and applications.\u201d SICOMP 18 (1989) 30\u201355.","journal-title":"SICOMP"},{"key":"32_CR13","unstructured":"A. Gupta. \u201cSteiner points in tree metrics don\u2019t (really) help.\u201d In Proc. 12th SODA 2001, pp 220\u2013227."},{"key":"32_CR14","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1090\/qam\/184873","volume":"22","author":"S. L. Hakimi","year":"1964","unstructured":"S. L. Hakimi and S. S. Yau. \u201cDistance matrix of a graph and its realizability.\u201d Quart. Appl. Math. 22 (1964), 305\u2013317.","journal-title":"Quart. Appl. Math"},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. \u201cSome optimal inapproximability results.\u201d In Proc STOC (1997) 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"32_CR16","doi-asserted-by":"crossref","unstructured":"S. Khot. \u201cImproved inapproximability results for max clique, chromatic number and approximate graph coloring.\u201d In Proc FOCS (2001).","DOI":"10.1109\/SFCS.2001.959936"},{"issue":"1\u20132","key":"32_CR17","first-page":"29","volume":"12","author":"J. Nieminen","year":"1976","unstructured":"J. Nieminen. \u201cRealizing the distance matrix of a graph.\u201d Elektron. Informationsverarbeit. Kybernetik 12(1\u20132):1976, 29\u201331.","journal-title":"Elektron. Informationsverarbeit. Kybernetik"},{"issue":"3","key":"32_CR18","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0012-365X(90)90337-H","volume":"79","author":"J. Pereira","year":"1990","unstructured":"J. Pereira. \u201cAn algorithm and its role in the study of optimal graph realizations of distance matrices.\u201d Discrete Math. 79(3):1990, 299\u2013312.","journal-title":"Discrete Math"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"S. B. Rao and W. D. Smith. \u201cImproved approximation schemes for geometrical graphs via spanners and banyans.\u201d In Proc. STOC (1998), 540\u2013550.","DOI":"10.1145\/276698.276868"}],"container-title":["Lecture Notes in Computer Science","STACS 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36494-3_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T18:55:15Z","timestamp":1558983315000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36494-3_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540006237","9783540364948"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-36494-3_32","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]}}}