{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:54:06Z","timestamp":1780073646314,"version":"3.54.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T00:00:00Z","timestamp":1667865600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T00:00:00Z","timestamp":1667865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018043"],"award-info":[{"award-number":["2018043"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,3]]},"DOI":"10.1007\/s00453-022-01055-2","type":"journal-article","created":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T16:11:09Z","timestamp":1667923869000},"page":"665-687","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Composed Degree-Distance Realizations of Graphs"],"prefix":"10.1007","volume":"85","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":"Dror","family":"Rawitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,11,8]]},"reference":[{"key":"1055_CR1","doi-asserted-by":"crossref","unstructured":"Bar-Noy, A., B\u00f6hnlein, T., Peleg, D., Perry, M., Rawitz, D.: Relaxed and approximate graph realizations. In: 32nd IWOCA. LNCS, vol. 12757, pp. 3\u201319 (2021)","DOI":"10.1007\/978-3-030-79987-8_1"},{"key":"1055_CR2","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1137\/15M102527X","volume":"31","author":"D Burstein","year":"2017","unstructured":"Burstein, D., Rubin, J.: Sufficient conditions for graphicality of bidegree sequences. SIAM J. Discrete Math. 31, 50\u201362 (2017)","journal-title":"SIAM J. Discrete Math."},{"key":"1055_CR3","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.2140\/pjm.1957.7.1073","volume":"7","author":"D Gale","year":"1957","unstructured":"Gale, D.: A theorem on flows in networks. Pac. J. Math. 7, 1073\u20131082 (1957)","journal-title":"Pac. J. Math."},{"key":"1055_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10587-007-0042-z","volume":"57","author":"G Gupta","year":"2007","unstructured":"Gupta, G., Joshi, P., Tripathi, A.: Graphic sequences of trees and a problem of Frobenius. Czechoslov. Math. J. 57, 49\u201352 (2007)","journal-title":"Czechoslov. Math. J."},{"key":"1055_CR5","doi-asserted-by":"publisher","first-page":"371","DOI":"10.4153\/CJM-1957-044-3","volume":"9","author":"HJ Ryser","year":"1957","unstructured":"Ryser, H.J.: Combinatorial properties of matrices of zeros and ones. Can. J. Math. 9, 371\u2013377 (1957)","journal-title":"Can. J. Math."},{"issue":"1\u20133","key":"1055_CR6","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0012-365X(92)90152-6","volume":"105","author":"IE Zverovich","year":"1992","unstructured":"Zverovich, I.E., Zverovich, V.E.: Contributions to the theory of graphic sequences. Discrete Math. 105(1\u20133), 293\u2013303 (1992)","journal-title":"Discrete Math."},{"key":"1055_CR7","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":"1055_CR8","unstructured":"Baldisserri, A.: Buneman\u2019s theorem for trees with exactly n vertices. CoRR (2014)"},{"key":"1055_CR9","unstructured":"Bar-Noy, A., Peleg, D., Perry, M., Rawitz, D., Schwartz, N.L.: Distance Realization Approximations. Manuscript (2021)"},{"key":"1055_CR10","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":"1055_CR11","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 International Symposium on Circuits and Systems (ISCAS), pp. 2545\u20132548 (1993)","DOI":"10.1109\/ISCAS.1993.693210"},{"key":"1055_CR12","doi-asserted-by":"crossref","unstructured":"Asano, T.: Graphical degree sequence problems with connectivity requirements. In: 4th ISAAC. LNCS, vol. 762, pp. 38\u201347 (1993)","DOI":"10.1007\/3-540-57568-5_233"},{"issue":"2","key":"1055_CR13","doi-asserted-by":"publisher","first-page":"73","DOI":"10.6028\/jres.068B.013","volume":"68B","author":"J Edmonds","year":"1964","unstructured":"Edmonds, J.: Existence of $$k$$-edge-connected ordinary graphs with prescribed degrees. J. Res. Natl. Bur. Stand. 68B(2), 73\u201374 (1964)","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"1055_CR14","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1002\/net.3230030303","volume":"3","author":"DL Wang","year":"1973","unstructured":"Wang, D.L., Kleitman, D.J.: On the existence of $$n$$-connected graphs with prescribed degrees ($$n>2$$). Networks 3, 225\u2013239 (1973)","journal-title":"Networks"},{"key":"1055_CR15","doi-asserted-by":"crossref","unstructured":"Rao, S.B.: A survey of the theory of potentially p-graphic and forcibly p-graphic degree sequences. In: Combinatorics and Graph Theory. LNM, vol. 885, pp. 417\u2013440 (1981)","DOI":"10.1007\/BFb0092288"},{"key":"1055_CR16","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. Discret. Comput. Geom. 3, 103\u2013122 (1988)","journal-title":"Discret. Comput. Geom."},{"issue":"1","key":"1055_CR17","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."},{"key":"1055_CR18","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":"1055_CR19","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":"1055_CR20","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":"1055_CR21","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":"1055_CR22","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. Math. 53, 321\u2013402 (1984)","journal-title":"Adv. Math."},{"key":"1055_CR23","doi-asserted-by":"crossref","unstructured":"Feder, T., Meyerson, A., Motwani, R., O\u2019Callaghan, L., Panigrahy, R.: Representing graph metrics with fewest edges. In: 20th STACS. LNCS, vol. 2607, pp. 355\u2013366 (2003)","DOI":"10.1007\/3-540-36494-3_32"},{"issue":"1","key":"1055_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0095-8956(84)90009-1","volume":"36","author":"W Imrich","year":"1984","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)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1\/2","key":"1055_CR25","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."},{"issue":"3","key":"1055_CR26","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1090\/qam\/414405","volume":"30","author":"AN Patrinos","year":"1972","unstructured":"Patrinos, A.N., Hakimi, S.L.: The distance matrix of a graph nand its tree realizability. Quart. Appl. Math. 30(3), 255\u2013269 (1972)","journal-title":"Quart. Appl. Math."},{"key":"1055_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. Comb. Theory B 6, 303\u2013310 (1969)","journal-title":"J. Comb. Theory B"},{"key":"1055_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":"1055_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":"1055_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."},{"issue":"1","key":"1055_CR31","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":"1055_CR32","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"},{"issue":"3","key":"1055_CR33","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0012-365X(76)90098-4","volume":"16","author":"M Behzad","year":"1976","unstructured":"Behzad, M., Simpson, J.E.: Eccentric sequences and eccentric sets in graphs. Discret. Math. 16(3), 187\u2013193 (1976)","journal-title":"Discret. Math."},{"issue":"4","key":"1055_CR34","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF02017925","volume":"6","author":"L Lesniak","year":"1975","unstructured":"Lesniak, L.: Eccentric sequences in graphs. Period. Math. Hung. 6(4), 287\u2013293 (1975)","journal-title":"Period. Math. Hung."},{"issue":"4","key":"1055_CR35","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"RE Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9(4), 551\u2013570 (1961)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"1055_CR36","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1109\/TCT.1970.1083185","volume":"CT\u201317","author":"H Frank","year":"1970","unstructured":"Frank, H., Chou, W.: Connectivity considerations in the design of survivable networks. IEEE Trans. Circuit Theory CT\u201317, 486\u2013490 (1970)","journal-title":"IEEE Trans. Circuit Theory"},{"key":"1055_CR37","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1137\/0405003","volume":"5","author":"A Frank","year":"1992","unstructured":"Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math. 5, 25\u201343 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"1055_CR38","unstructured":"Frank, A.: Connectivity augmentation problems in network design. In: Mathematical Programming: State of the Art, pp. 34\u201363 (1994)"},{"key":"1055_CR39","unstructured":"Bar-Noy, A., Choudhary, K., Peleg, D., Rawitz, D.: Graph realizations: maximum degree in vertex neighborhoods. In: 17th SWAT. LIPIcs, vol. 162, pp. 10\u201311017 (2020)"},{"key":"1055_CR40","unstructured":"Bar-Noy, A., Choudhary, K., Cohen, A., Peleg, D., Rawitz, D.: Minimum neighboring degree realization in graphs and trees. In: 28th ESA. LIPIcs, vol. 173, pp. 10\u201311015 (2020)"},{"key":"1055_CR41","doi-asserted-by":"crossref","unstructured":"Bar-Noy, A., Choudhary, K., Peleg, D., Rawitz, D.: Realizability of graph specifications: Characterizations and algorithms. In: 25th SIROCCO. LNCS, vol. 11085, pp. 3\u201313 (2018)","DOI":"10.1007\/978-3-030-01325-7_1"},{"key":"1055_CR42","unstructured":"Bar-Noy, A., Choudhary, K., Peleg, D., Rawitz, D.: Graph profile realizations and applications to social networks. In: 13th WALCOM. LNCS, vol. 11355, pp. 1\u201312 (2019)"},{"issue":"1","key":"1055_CR43","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/0196-6774(85)90022-7","volume":"6","author":"RP Anstee","year":"1985","unstructured":"Anstee, R.P.: An algorithmic proof of tutte\u2019s $$f$$-factor theorem. J. Algorithms 6(1), 112\u2013131 (1985)","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01055-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01055-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01055-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T18:17:08Z","timestamp":1728325028000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01055-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,8]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["1055"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01055-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,8]]},"assertion":[{"value":"30 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}