{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,24]],"date-time":"2026-05-24T06:05:04Z","timestamp":1779602704559,"version":"3.53.1"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032264640","type":"print"},{"value":"9783032264657","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-26465-7_5","type":"book-chapter","created":{"date-parts":[[2026,5,24]],"date-time":"2026-05-24T05:49:26Z","timestamp":1779601766000},"page":"73-92","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimum Deviation Distance Realization"],"prefix":"10.1007","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mor","family":"Perry","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yingli","family":"Ran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,24]]},"reference":[{"issue":"2","key":"5_CR1","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BF02187901","volume":"3","author":"I Alth\u00f6fer","year":"1988","unstructured":"Alth\u00f6fer, I.: On optimal realizations of finite metric spaces by graphs. Discr. Comput. Geometry 3(2), 103\u2013122 (1988). https:\/\/doi.org\/10.1007\/BF02187901","journal-title":"Discr. Comput. Geometry"},{"key":"5_CR2","unstructured":"Baldisserri, A.: Buneman\u2019s theorem for trees with exatcly $$n$$ vertices. Tech. Rep. 1407.0048, arXiv (2014)"},{"issue":"2","key":"5_CR3","first-page":"185","volume":"70","author":"A Baldisserri","year":"2018","unstructured":"Baldisserri, A., Rubei, E.: Distance matrices of some positive-weighted graphs. Australian J. Combinat. 70(2), 185\u2013201 (2018)","journal-title":"Australian J. Combinat."},{"issue":"1","key":"5_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0403001","volume":"3","author":"H Bandelt","year":"1990","unstructured":"Bandelt, H.: Recognition of tree metrics. SIAM J. Discret. Math. 3(1), 1\u20136 (1990)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"5_CR5","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1007\/s00453-022-01055-2","volume":"85","author":"A Bar-Noy","year":"2023","unstructured":"Bar-Noy, A., Peleg, D., Perry, M., Rawitz, D.: Composed degree-distance realizations of graphs. Algorithmica 85(3), 665\u2013687 (2023)","journal-title":"Algorithmica"},{"key":"5_CR6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.114810","volume":"1019","author":"A Bar-Noy","year":"2024","unstructured":"Bar-Noy, A., Peleg, D., Perry, M., Rawitz, D.: Graph realization of distance sets. Theor. Comput. Sci. 1019, 114810 (2024)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"5_CR7","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/060653391","volume":"30","author":"J Brickell","year":"2008","unstructured":"Brickell, J., Dhillon, I.S., Sra, S., Tropp, J.A.: The metric nearness problem. SIAM J. Matrix Anal. Appl. 30(1), 375\u2013396 (2008)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/0095-8956(74)90047-1","volume":"17","author":"P Buneman","year":"1974","unstructured":"Buneman, P.: A note on the metric properties of trees. J. Combinat. Theory B 17, 48\u201350 (1974)","journal-title":"J. Combinat. Theory B"},{"issue":"3","key":"5_CR9","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1006\/jcss.2001.1785","volume":"63","author":"FRK Chung","year":"2001","unstructured":"Chung, F.R.K., Garrett, M.W., Graham, R.L., Shallcross, D.: Distance realization problems with applications to internet tomography. J. Comput. Syst. Sci. 63(3), 432\u2013448 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"5_CR10","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(89)90216-0","volume":"30","author":"JC Culberson","year":"1989","unstructured":"Culberson, J.C., Rudnicki, P.: A fast algorithm for constructing trees from distance matrices. Inf. Process. Lett. 30(4), 215\u2013220 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"5_CR11","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1137\/0406041","volume":"6","author":"E Dahlhaus","year":"1993","unstructured":"Dahlhaus, E.: Fast parallel recognition of ultrametrics and tree metrics. SIAM J. Discret. Math. 6(4), 523\u2013532 (1993)","journal-title":"SIAM J. Discret. Math."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Dinur, I., Khot, S., Kindler, G., Minzer, D., Safra, M.: Towards a proof of the 2-to-1 games conjecture? In: 50th ACM STOC, pp. 376\u2013389 (2018)","DOI":"10.1145\/3188745.3188804"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0001-8708(84)90029-X","volume":"53","author":"AWM Dress","year":"1984","unstructured":"Dress, A.W.M.: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces. Adv. in Math. 53, 321\u2013402 (1984)","journal-title":"Adv. in Math."},{"key":"5_CR14","unstructured":"Fan, C., Gilbert, A.C., Raichel, B., Sonthalia, R., Buskirk, G.V.: Generalized metric repair on graphs. In: 17th SWAT. LIPIcs, vol.\u00a0162, pp. 25:1\u201325:22 (2020)"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"Fan, C., Raichel, B., Buskirk, G.V.: Metric violation distance: Hardness and approximation. In: 28th ACM-SIAM SODA, pp. 196\u2013209 (2018)","DOI":"10.1137\/1.9781611975031.14"},{"key":"5_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/3-540-36494-3_32","volume-title":"STACS 2003","author":"T Feder","year":"2003","unstructured":"Feder, T., Meyerson, A., Motwani, R., O\u2019Callaghan, L., Panigrahy, R.: Representing graph metrics with fewest edges. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 355\u2013366. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-36494-3_32"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Jain, L.: If it ain\u2019t broke, don\u2019t fix it: Sparse metric repair. In: 55th IEEE Allerton Conference on Communication, Control, and Compution, pp. 612\u2013619 (2017)","DOI":"10.1109\/ALLERTON.2017.8262793"},{"key":"5_CR18","first-page":"169","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Comb. 1, 169\u2013197 (1981)","journal-title":"Comb."},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1090\/qam\/184873","volume":"22","author":"SL Hakimi","year":"1965","unstructured":"Hakimi, S.L., Yau, S.S.: Distance matrix of a graph and its realizability. Quart. Appl. Math. 22, 305\u2013317 (1965)","journal-title":"Quart. Appl. Math."},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Imrich, W., Sim\u00f5es-Pereira, J.M.S., Zamfirescu, C.: On optimal embeddings of metrics in graphs. J. Comb. Theory, Ser. B 36(1), 1\u201315 (1984)","DOI":"10.1016\/0095-8956(84)90009-1"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"Khot, S., Minzer, D., Safra, M.: On independent sets, 2-to-2 games, and grassmann graphs. In: 49th ACM STOC, pp. 576\u2013589 (2017)","DOI":"10.1145\/3055399.3055432"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"Khot, S., Minzer, D., Safra, M.: Pseudorandom sets in grassmann graph have near-perfect expansion. In: 59th IEEE FOCS, pp. 592\u2013601 (2018)","DOI":"10.1109\/FOCS.2018.00062"},{"issue":"3","key":"5_CR23","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\/2","key":"5_CR24","first-page":"29","volume":"12","author":"J Nieminen","year":"1976","unstructured":"Nieminen, J.: Realizing the distance matrix of a graph. J. Inf. Process. Cybern. 12(1\/2), 29\u201331 (1976)","journal-title":"J. Inf. Process. Cybern."},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Patrinos, A.N., Hakimi, S.L.: The distance matrix of a graph n and its tree realizability. Quart. Appl. Math. 255 (1972)","DOI":"10.1090\/qam\/414405"},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/s00357-016-9206-6","volume":"33","author":"E Rubei","year":"2016","unstructured":"Rubei, E.: Weighted graphs with distances in given ranges. J. Classif. 33, 282\u2013297 (2016)","journal-title":"J. Classif."},{"key":"5_CR27","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0021-9800(69)80092-X","volume":"6","author":"JMS Sim\u00f5es-Pereira","year":"1969","unstructured":"Sim\u00f5es-Pereira, J.M.S.: A note on the tree realizability of a distance matrix. J. Combinat. Theory B 6, 303\u2013310 (1969)","journal-title":"J. Combinat. Theory B"},{"key":"5_CR28","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0012-365X(87)90059-8","volume":"65","author":"JMS Sim\u00f5es-Pereira","year":"1987","unstructured":"Sim\u00f5es-Pereira, J.M.S.: A note on distance matrices with unicyclic graph realizations. Discret. Math. 65, 277\u2013287 (1987)","journal-title":"Discret. Math."},{"issue":"2","key":"5_CR29","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/0401023","volume":"1","author":"JMS Sim\u00f5es-Pereira","year":"1988","unstructured":"Sim\u00f5es-Pereira, J.M.S.: An optimality criterion for graph embeddings of metrics. SIAM J. Discret. Math. 1(2), 223\u2013229 (1988)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"5_CR30","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0012-365X(90)90337-H","volume":"79","author":"JMS Sim\u00f5es-Pereira","year":"1990","unstructured":"Sim\u00f5es-Pereira, J.M.S.: An algorithm and its role in the study of optimal graph realizations of distance matrices. Discret. Math. 79(3), 299\u2013312 (1990)","journal-title":"Discret. Math."},{"key":"5_CR31","doi-asserted-by":"crossref","unstructured":"Tamura, H., Sengoku, M., Shinoda, S., Abe, T.: Realization of a network from the upper and lower bounds of the distances (or capacities) between vertices. In: IEEE ISCAS, pp. 2545\u20132548 (1993)","DOI":"10.1109\/ISCAS.1993.693210"},{"issue":"1","key":"5_CR32","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.ejor.2005.02.071","volume":"174","author":"SC Varone","year":"2006","unstructured":"Varone, S.C.: A constructive algorithm for realizing a distance matrix. Eur. J. Oper. Res. 174(1), 102\u2013111 (2006)","journal-title":"Eur. J. Oper. Res."},{"key":"5_CR33","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer (2001)"},{"key":"5_CR34","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511921735"},{"key":"5_CR35","first-page":"90","volume":"20","author":"KA Zaretskii","year":"1965","unstructured":"Zaretskii, K.A.: Constructing a tree on the basis of a set of distances between the hanging vertices. Uspekhi Mat. Nauk 20, 90\u201392 (1965)","journal-title":"Uspekhi Mat. Nauk"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-26465-7_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,24]],"date-time":"2026-05-24T05:49:29Z","timestamp":1779601769000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-26465-7_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032264640","9783032264657"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-26465-7_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"24 May 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Durham","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"33","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sirocco2026.webspace.durham.ac.uk\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}