{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T08:45:28Z","timestamp":1743497128832,"version":"3.40.3"},"publisher-location":"Cham","reference-count":102,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030799861"},{"type":"electronic","value":"9783030799878"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79987-8_1","type":"book-chapter","created":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:05:05Z","timestamp":1625007905000},"page":"3-19","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Relaxed and Approximate Graph Realizations"],"prefix":"10.1007","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[]},{"given":"Toni","family":"B\u00f6hnlein","sequence":"additional","affiliation":[]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[]},{"given":"Mor","family":"Perry","sequence":"additional","affiliation":[]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,30]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/j.disc.2018.10.013","volume":"342","author":"P Adams","year":"2019","unstructured":"Adams, P., Nikolayevsky, Y.: Planar bipartite biregular degree sequences. Discr. Math. 342, 433\u2013440 (2019)","journal-title":"Discr. Math."},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0012-365X(94)00104-Q","volume":"136","author":"M Aigner","year":"1994","unstructured":"Aigner, M., Triesch, E.: Realizability and uniqueness in graphs. Discr. Math. 136, 3\u201320 (1994)","journal-title":"Discr. Math."},{"issue":"4","key":"1_CR3","doi-asserted-by":"publisher","first-page":"321","DOI":"10.3233\/FI-2017-1588","volume":"155","author":"A Alpers","year":"2017","unstructured":"Alpers, A., Gritzmann, P.: Reconstructing binary matrices under window constraints from their row and column sums. Fundamenta Informaticae 155(4), 321\u2013340 (2017)","journal-title":"Fundamenta Informaticae"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Alpers, A., Gritzmann, P.: Dynamic discrete tomography. Inverse Probl. 34(3), 034003 (2018)","DOI":"10.1088\/1361-6420\/aaa202"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"1369","DOI":"10.1137\/17M1115629","volume":"32","author":"A Alpers","year":"2018","unstructured":"Alpers, A., Gritzmann, P.: On double-resolution imaging and discrete tomography. SIAM J. Discr. Math. 32, 1369\u20131399 (2018)","journal-title":"SIAM J. Discr. Math."},{"key":"1_CR6","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."},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"438","DOI":"10.4153\/CJM-1982-029-3","volume":"34","author":"R Anstee","year":"1982","unstructured":"Anstee, R.: Properties of a class of (0,1)-matrices covering a given matrix. Canad. J. Math. 34, 438\u2013453 (1982)","journal-title":"Canad. J. Math."},{"issue":"1","key":"1_CR8","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"},{"key":"1_CR9","unstructured":"Baldisserri, A.: Buneman\u2019s theorem for trees with exactly n vertices. CoRR (2014)"},{"key":"1_CR10","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. Discr. Math. 3, 1\u20136 (1990)","journal-title":"SIAM J. Discr. Math."},{"key":"1_CR11","unstructured":"Bar-Noy, A., B\u00f6hnlein, T., Lotker, Z., Peleg, D., Rawitz, D.: The generalized microscopic image reconstruction problem. In: 30th ISAAC, volume 149 of LIPIcs, pp. 42:1\u201342:15 (2019)"},{"issue":"4","key":"1_CR12","doi-asserted-by":"publisher","first-page":"2318","DOI":"10.1137\/20M1326489","volume":"34","author":"A Bar-Noy","year":"2020","unstructured":"Bar-Noy, A., Choudhary, K., Peleg, D., Rawitz, D.: Efficiently realizing interval sequences. SIAM J. Discr. Math. 34(4), 2318\u20132337 (2020)","journal-title":"SIAM J. Discr. Math."},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Bar-Noy, A., Peleg, D., Perry, M., Rawitz, D.: Composed degree-distance realizations of graphs. In: 32nd IWOCA (2021)","DOI":"10.1007\/s00453-022-01055-2"},{"key":"1_CR14","unstructured":"Bar-Noy, A., Peleg, D., Perry, M., Rawitz, D., Schwartz, N. L.: Distance realization approximations. In: preparation (2021)"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/j.cviu.2012.09.009","volume":"117","author":"D Battaglino","year":"2013","unstructured":"Battaglino, D., Frosini, A., Rinaldi, S.: A decomposition theorem for homogeneous sets with respect to diamond probes. Comput. Vis. Image Underst. 117, 319\u2013325 (2013)","journal-title":"Comput. Vis. Image Underst."},{"key":"1_CR16","volume-title":"Tree Thinking: an Introduction to Phylogenetic Biology","author":"DA Baum","year":"2013","unstructured":"Baum, D.A., Smith, S.D.: Tree Thinking: an Introduction to Phylogenetic Biology. Roberts and Company, Greenwood Village, CO (2013)"},{"issue":"4","key":"1_CR17","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1080\/15427951.2010.557277","volume":"6","author":"JK Blitzstein","year":"2011","unstructured":"Blitzstein, J.K., Diaconis, P.: A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet Math. 6(4), 489\u2013522 (2011)","journal-title":"Internet Math."},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/j.jtbi.2013.06.024","volume":"335","author":"M Broom","year":"2013","unstructured":"Broom, M., Cannings, C.: A dynamic network population model with strategic link formation governed by individual preferences. J. Theoret. Biol. 335, 160\u2013168 (2013)","journal-title":"J. Theoret. Biol."},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1016\/j.disc.2014.12.011","volume":"338","author":"M Broom","year":"2015","unstructured":"Broom, M., Cannings, C.: Graphic deviation. Discr. Math. 338, 701\u2013711 (2015)","journal-title":"Discr. Math."},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"285","DOI":"10.3934\/jdg.2017016","volume":"335","author":"M Broom","year":"2017","unstructured":"Broom, M., Cannings, C.: Game theoretical modelling of a dynamically evolving network i: general target sequences. J. Dyn. Games 335, 285\u2013318 (2017)","journal-title":"J. Dyn. Games"},{"key":"1_CR21","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. Discr. Math. 31, 50\u201362 (2017)","journal-title":"SIAM J. Discr. Math."},{"issue":"1\u20133","key":"1_CR22","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0012-365X(00)00022-4","volume":"219","author":"M-C Cai","year":"2000","unstructured":"Cai, M.-C., Deng, X., Zang, W.: Solution to a problem on degree sequences of graphs. Discr. Math. 219(1\u20133), 253\u2013257 (2000)","journal-title":"Discr. Math."},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"311","DOI":"10.2307\/2406441","volume":"19","author":"JH Camin","year":"1965","unstructured":"Camin, J.H., Sokal, R.R.: A method for deducing branching sequences in phylogeny. Evolution 19, 311\u2013326 (1965)","journal-title":"Evolution"},{"issue":"5","key":"1_CR24","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/0016-0032(66)90301-2","volume":"281","author":"W-K Chen","year":"1966","unstructured":"Chen, W.-K.: On the realization of a (p, s)-digraph with prescribed degrees. J. Franklin Inst. 281(5), 406\u2013422 (1966)","journal-title":"J. Franklin Inst."},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0012-365X(87)90184-1","volume":"64","author":"AA Chernyak","year":"1987","unstructured":"Chernyak, A.A., Chernyak, Z.A., Tyshkevich, R.I.: On forcibly hereditary $$p$$-graphical sequences. Discr. Math. 64, 111\u2013128 (1987)","journal-title":"Discr. Math."},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"W. Chou and H. Frank. Survivable communication networks and the terminal capacity matrix. IEEE Trans. Circ. Theory, CT-17, 192\u2013197 (1970)","DOI":"10.1109\/TCT.1970.1083100"},{"issue":"1","key":"1_CR27","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1017\/S0004972700002872","volume":"33","author":"SA Choudum","year":"1991","unstructured":"Choudum, S.A.: A simple proof of the Erd\u00f6s-Gallai theorem on graph sequences. Bull. Austral. Math. Soc. 33(1), 67\u201370 (1991)","journal-title":"Bull. Austral. Math. Soc."},{"key":"1_CR28","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, 432\u2013448 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"1_CR29","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0012-365X(74)80016-6","volume":"7","author":"V Chungphaisan","year":"1974","unstructured":"Chungphaisan, V.: Conditions for sequences to be r-graphic. Discr. Math. 7(1\u20132), 31\u201339 (1974)","journal-title":"Discr. Math."},{"issue":"3","key":"1_CR30","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1080\/15427951.2016.1164768","volume":"12","author":"B Cloteaux","year":"2016","unstructured":"Cloteaux, B.: Fast sequential creation of random realizations of degree sequences. Internet Math. 12(3), 205\u2013219 (2016)","journal-title":"Internet Math."},{"issue":"4","key":"1_CR31","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":"1\u20133","key":"1_CR32","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.disc.2005.09.005","volume":"304","author":"G Dahl","year":"2005","unstructured":"Dahl, G., Flatberg, T.: A remark concerning graphical sequences. Discr. Math. 304(1\u20133), 62\u201364 (2005)","journal-title":"Discr. Math."},{"issue":"4","key":"1_CR33","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. Discr. Math. 6(4), 523\u2013532 (1993)","journal-title":"SIAM J. Discr. Math."},{"key":"1_CR34","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":"1_CR35","doi-asserted-by":"crossref","unstructured":"Erd\u00f6s, D., Gemulla, R., Terzi, E.: Reconstructing graphs from neighborhood data. ACM Trans. Knowl. Discov. Data 8(4), 23:1\u201323:22 (2014)","DOI":"10.1145\/2641761"},{"key":"1_CR36","first-page":"264","volume":"11","author":"P Erd\u00f6s","year":"1960","unstructured":"Erd\u00f6s, P., Gallai, T.: Graphs with prescribed degrees of vertices [Hungarian]. Matematikai Lapok 11, 264\u2013274 (1960)","journal-title":"Matematikai Lapok"},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"Erd\u00f6s, P.L., Mikl\u00f3s, I., Toroczkai, Z.: A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs. Electr. J. Comb. 17(1) (2010)","DOI":"10.37236\/338"},{"issue":"2","key":"1_CR38","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/s00224-018-9863-4","volume":"63","author":"G Even","year":"2019","unstructured":"Even, G., Medina, M., Patt-Shamir, B.: On-line path computation and function placement in SDNs. Theory Comput. Syst. 63(2), 306\u2013325 (2019)","journal-title":"Theory Comput. Syst."},{"key":"1_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-319-48314-6_24","volume-title":"Structural Information and Communication Complexity","author":"G Even","year":"2016","unstructured":"Even, G., Rost, M., Schmid, S.: An approximation algorithm for path computation and function placement in SDNs. In: Suomela, J. (ed.) SIROCCO 2016. LNCS, vol. 9988, pp. 374\u2013390. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-48314-6_24"},{"key":"1_CR40","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":"1_CR41","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/BF01734359","volume":"17","author":"J Felsenstein","year":"1981","unstructured":"Felsenstein, J.: Evolutionary trees from DNA sequences: a maximum likelihood approach. J. Mol. Evol. 17, 368\u2013376 (1981)","journal-title":"J. Mol. Evol."},{"key":"1_CR42","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1093\/sysbio\/20.4.406","volume":"20","author":"WM Fitch","year":"1971","unstructured":"Fitch, W.M.: Toward defining the course of evolution: Minimum change for a specific tree topology. Syst. Biol. 20, 406\u2013416 (1971)","journal-title":"Syst. Biol."},{"key":"1_CR43","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. Discr. Math. 5, 25\u201343 (1992)","journal-title":"SIAM J. Discr. Math."},{"key":"1_CR44","unstructured":"Frank, A.: Connectivity augmentation problems in network design. In: Mathematical programming: state of the art, pp. 34\u201363. Univ. Michigan (1994)"},{"key":"1_CR45","doi-asserted-by":"crossref","unstructured":"Frank, H., Chou, W.: Connectivity considerations in the design of survivable networks. IEEE Trans. Circuit Theory, CT-17, 486\u2013490 (1970)","DOI":"10.1109\/TCT.1970.1083185"},{"issue":"1\u20133","key":"1_CR46","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/j.tcs.2006.10.030","volume":"370","author":"A Frosini","year":"2007","unstructured":"Frosini, A., Nivat, M.: Binary matrices under the microscope: a tomographical problem. Theor. Comput. Sci. 370(1\u20133), 201\u2013217 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"1_CR47","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.tcs.2008.07.016","volume":"406","author":"A Frosini","year":"2008","unstructured":"Frosini, A., Nivat, M., Rinaldi, S.: Scanning integer matrices by means of two rectangular windows. Theor. Comput. Sci. 406(1\u20132), 90\u201396 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR48","doi-asserted-by":"publisher","first-page":"831","DOI":"10.2140\/pjm.1960.10.831","volume":"12","author":"D Fulkerson","year":"1960","unstructured":"Fulkerson, D.: Zero-one matrices with zero trace. Pacific J. Math. 12, 831\u2013836 (1960)","journal-title":"Pacific J. Math."},{"key":"1_CR49","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. Pacific J. Math. 7, 1073\u20131082 (1957)","journal-title":"Pacific J. Math."},{"issue":"17","key":"1_CR50","doi-asserted-by":"publisher","first-page":"2170","DOI":"10.1016\/j.dam.2011.06.017","volume":"159","author":"A Garg","year":"2011","unstructured":"Garg, A., Goel, A., Tripathi, A.: Constructive extensions of two results on graphic sequences. Discr. Appl. Math. 159(17), 2170\u20132174 (2011)","journal-title":"Discr. Appl. Math."},{"key":"1_CR51","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s12052-011-0355-0","volume":"4","author":"N Gontier","year":"2011","unstructured":"Gontier, N.: Depicting the tree of life: the philosophical and historical roots of evolutionary tree diagrams. Evol. Educ. Outreach 4, 515\u2013538 (2011)","journal-title":"Evol. Educ. Outreach"},{"key":"1_CR52","doi-asserted-by":"publisher","first-page":"1589","DOI":"10.1137\/100803262","volume":"25","author":"P Gritzmann","year":"2011","unstructured":"Gritzmann, P., Langfeld, B., Wiegelmann, M.: Uniqueness in discrete tomography: three remarks and a corollary. SIAM J. Discr. Math. 25, 1589\u20131599 (2011)","journal-title":"SIAM J. Discr. Math."},{"key":"1_CR53","first-page":"287","volume":"16","author":"J Guo","year":"2014","unstructured":"Guo, J., Yin, J.: A variant of Niessen\u2019s problem on degree sequences of graphs. Discr. Math. Theor. Comput. Sci. 16, 287\u2013292 (2014)","journal-title":"Discr. Math. Theor. Comput. Sci."},{"key":"1_CR54","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. Czechoslovak Math. J. 57, 49\u201352 (2007)","journal-title":"Czechoslovak Math. J."},{"issue":"3","key":"1_CR55","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/0110037","volume":"10","author":"SL Hakimi","year":"1962","unstructured":"Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph -I. SIAM J. Appl. Math. 10(3), 496\u2013506 (1962)","journal-title":"SIAM J. Appl. Math."},{"key":"1_CR56","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."},{"issue":"1","key":"1_CR57","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1137\/0602006","volume":"2","author":"PL Hammer","year":"1981","unstructured":"Hammer, P.L., Ibaraki, T., Simeone, B.: Threshold sequences. SIAM J. Algebra. Discr. 2(1), 39\u201349 (1981)","journal-title":"SIAM J. Algebra. Discr."},{"key":"1_CR58","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF02579333","volume":"1","author":"PL Hammer","year":"1981","unstructured":"Hammer, P.L., Simeone, B.: The splittance of a graph. Combinatorica 1, 275\u2013284 (1981)","journal-title":"Combinatorica"},{"key":"1_CR59","doi-asserted-by":"publisher","first-page":"1931","DOI":"10.1137\/130935756","volume":"29","author":"S Hartung","year":"2015","unstructured":"Hartung, S., Nichterlein, A.: Np-hardness and fixed-parameter tractability of realizing degree sequences with directed acyclic graphs. SIAM J. Discr. Math. 29, 1931\u20131960 (2015)","journal-title":"SIAM J. Discr. Math."},{"key":"1_CR60","doi-asserted-by":"publisher","first-page":"477","DOI":"10.21136\/CPM.1955.108220","volume":"80","author":"V Havel","year":"1955","unstructured":"Havel, V.: A remark on the existence of finite graphs [in Czech]. Casopis Pest. Mat. 80, 477\u2013480 (1955)","journal-title":"Casopis Pest. Mat."},{"key":"1_CR61","doi-asserted-by":"crossref","unstructured":"Heinrich, K., Hell, P., Kirkpatrick, D.G., Liu, G.: A simple existence criterion for $$(g < f)$$-factors. Discr. Math. 85, 313\u2013317 (1990)","DOI":"10.1016\/0012-365X(90)90387-W"},{"issue":"18","key":"1_CR62","doi-asserted-by":"publisher","first-page":"5703","DOI":"10.1016\/j.disc.2008.05.005","volume":"309","author":"P Hell","year":"2009","unstructured":"Hell, P., Kirkpatrick, D.: Linear-time certifying algorithms for near-graphical sequences. Discr. Math. 309(18), 5703\u20135713 (2009)","journal-title":"Discr. Math."},{"key":"1_CR63","unstructured":"Hennig, W.: Phylogenetic Systematics. Illinois University Press, Champaign (1966)"},{"key":"1_CR64","unstructured":"Herman, G.T., Kuba, A.: Discrete Tomography: Foundations, Algorithms, and Applications. Springer Science & Business Media (2012)"},{"issue":"5","key":"1_CR65","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1016\/j.orl.2008.05.004","volume":"36","author":"H Hulett","year":"2008","unstructured":"Hulett, H., Will, T.G., Woeginger, G.J.: Multigraph realizations of degree sequences: maximization is easy, minimization is hard. Oper. Res. Lett. 36(5), 594\u2013596 (2008)","journal-title":"Oper. Res. Lett."},{"key":"1_CR66","unstructured":"Jayadev, S.P., Narasimhan, S., Bhatt, N.: Learning conserved networks from flows. Technical report, CoRR (2019). http:\/\/arxiv.org\/abs\/1905.08716"},{"key":"1_CR67","doi-asserted-by":"publisher","first-page":"961","DOI":"10.2140\/pjm.1957.7.961","volume":"7","author":"P Kelly","year":"1957","unstructured":"Kelly, P.: A congruence theorem for trees. Pacific J. Math. 7, 961\u2013968 (1957)","journal-title":"Pacific J. Math."},{"key":"1_CR68","first-page":"235","volume":"23","author":"KK Kidd","year":"1971","unstructured":"Kidd, K.K., Sgaramella-Zonta, L.: Phylogenetic analysis: Concepts and methods. American J. Hum. Gen. 23, 235\u2013252 (1971)","journal-title":"American J. Hum. Gen."},{"key":"1_CR69","first-page":"1","volume":"42","author":"H Kim","year":"2009","unstructured":"Kim, H., Toroczkai, Z., Erdos, P.L., Miklos, I., Szekely, L.A.: Degree-based graph construction. J. Phys. Math. Theor. 42, 1\u201310 (2009)","journal-title":"J. Phys. Math. Theor."},{"issue":"1","key":"1_CR70","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1137\/0118005","volume":"18","author":"DJ Kleitman","year":"1970","unstructured":"Kleitman, D.J.: Minimal number of multiple edges in realization of an incidence sequence without loops. SIAM J. Appl. Math. 18(1), 25\u201328 (1970)","journal-title":"SIAM J. Appl. Math."},{"key":"1_CR71","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0012-365X(73)90037-X","volume":"6","author":"DJ Kleitman","year":"1973","unstructured":"Kleitman, D.J., Wang, D.L.: Algorithms for constructing graphs and digraphs with given valences and factors. Discr. Math. 6, 79\u201388 (1973)","journal-title":"Discr. Math."},{"key":"1_CR72","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.dam.2019.06.013","volume":"270","author":"G Kutiel","year":"2019","unstructured":"Kutiel, G., Rawitz, D.: Service chain placement in SDNs. Discr. Appl. Math. 270, 168\u2013180 (2019)","journal-title":"Discr. Appl. Math."},{"key":"1_CR73","doi-asserted-by":"crossref","unstructured":"Li, C., McCormick, S., Simchi-Levi, D.: On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems. Oper. Res. Lett. 11, 303\u2013308 (1992)","DOI":"10.1016\/0167-6377(92)90007-P"},{"key":"1_CR74","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/S0021-9800(70)80033-3","volume":"8","author":"L Lov\u00e1sz","year":"1970","unstructured":"Lov\u00e1sz, L.: Subgraphs with prescribed valencies. J. Comb. Theory 8, 391\u2013416 (1970)","journal-title":"J. Comb. Theory"},{"key":"1_CR75","unstructured":"Mihail, M., Vishnoi, N.: On generating graphs with prescribed degree sequences for complex network modeling applications. In: 3rd ARACNE (2002)"},{"issue":"1\/2","key":"1_CR76","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":"1","key":"1_CR77","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S1631-073X(02)02377-4","volume":"335","author":"M Nivat","year":"2002","unstructured":"Nivat, M.: Sous-ensembles homog\u00e9nes de z2 et pavages du plan. Comptes Rendus Mathematique 335(1), 83\u201386 (2002)","journal-title":"Comptes Rendus Mathematique"},{"key":"1_CR78","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1080\/00029890.1970.11992413","volume":"77","author":"PV O\u2019Neil","year":"1970","unstructured":"O\u2019Neil, P.V.: Ulam\u2019s conjecture and graph reconstructions. Am. Math. Mon. 77, 35\u201343 (1970)","journal-title":"Am. Math. Mon."},{"issue":"2","key":"1_CR79","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1137\/0115036","volume":"15","author":"A Owens","year":"1967","unstructured":"Owens, A., Trent, H.: On determining minimal singularities for the realizations of an incidence sequence. SIAM J. Appl. Math. 15(2), 406\u2013418 (1967)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"1_CR80","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1137\/0118019","volume":"18","author":"AB Owens","year":"1970","unstructured":"Owens, A.B.: On determining the minimum number of multiple edges for an incidence sequence. SIAM J. Appl. Math. 18(1), 238\u2013240 (1970)","journal-title":"SIAM J. Appl. Math."},{"key":"1_CR81","doi-asserted-by":"crossref","unstructured":"Patrinos, A.N., Hakimi, S.L.: The distance matrix of a graph n and its tree realizability. Q. Appl. Math. 30(3), 255 (1972)","DOI":"10.1090\/qam\/414405"},{"key":"1_CR82","doi-asserted-by":"publisher","first-page":"371","DOI":"10.4153\/CJM-1957-044-3","volume":"9","author":"H Ryser","year":"1957","unstructured":"Ryser, H.: Combinatorial properties of matrices of zeros and ones. Canad. J. Math. 9, 371\u2013377 (1957)","journal-title":"Canad. J. Math."},{"key":"1_CR83","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1137\/0132048","volume":"32","author":"EF Schmeichel","year":"1977","unstructured":"Schmeichel, E.F., Hakimi, S.L.: On planar graphical degree sequences. SIAM J. Appl. Math. 32, 598\u2013609 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"1_CR84","unstructured":"Schuh, R.T., Brower, A.V.: Biological Systematics: Principles and Applications. Cornell University Press (2009)"},{"issue":"2","key":"1_CR85","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/jgt.3190150209","volume":"15","author":"G Sierksma","year":"1991","unstructured":"Sierksma, G., Hoogeveen, H.: Seven criteria for integer sequences being graphic. J. Graph Theory 15(2), 223\u2013231 (1991)","journal-title":"J. Graph Theory"},{"issue":"2","key":"1_CR86","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. Discr. Math. 1(2), 223\u2013229 (1988)","journal-title":"SIAM J. Discr. Math."},{"issue":"3","key":"1_CR87","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. Discr. Math. 79(3), 299\u2013312 (1990)","journal-title":"Discr. Math."},{"key":"1_CR88","unstructured":"Swofford, D.L., Olsen, G.J.: Phylogeny reconstruction. Mol. Syst. 411\u2013501 (1990)"},{"key":"1_CR89","doi-asserted-by":"crossref","unstructured":"Tatsuya, A., Nagamochi, H.: Comparison and enumeration of chemical graphs. Comput. Struct. Biotechnol. 5(6), e201302004 (2013)","DOI":"10.5936\/csbj.201302004"},{"issue":"18","key":"1_CR90","doi-asserted-by":"publisher","first-page":"3513","DOI":"10.1016\/j.dam.2008.03.033","volume":"156","author":"A Tripathi","year":"2008","unstructured":"Tripathi, A., Tyagi, H.: A simple criterion on degree sequences of graphs. Discr. Appl. Math. 156(18), 3513\u20133517 (2008)","journal-title":"Discr. Appl. Math."},{"issue":"4","key":"1_CR91","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1016\/j.disc.2009.09.023","volume":"310","author":"A Tripathi","year":"2010","unstructured":"Tripathi, A., Venugopalan, S., West, D.B.: A short constructive proof of the Erd\u00f6s-Gallai characterization of graphic lists. Discr. Math. 310(4), 843\u2013844 (2010)","journal-title":"Discr. Math."},{"issue":"1\u20133","key":"1_CR92","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/S0012-365X(02)00886-5","volume":"265","author":"A Tripathi","year":"2003","unstructured":"Tripathi, A., Vijay, S.: A note on a theorem of Erd\u00f6s & Gallai. Discr. Math. 265(1\u20133), 417\u2013420 (2003)","journal-title":"Discr. Math."},{"key":"1_CR93","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF02579180","volume":"1","author":"WT Tutte","year":"1981","unstructured":"Tutte, W.T.: Graph factors. Combinatorica 1, 79\u201397 (1981)","journal-title":"Combinatorica"},{"key":"1_CR94","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0012-365X(99)00381-7","volume":"220","author":"R Tyshkevich","year":"2000","unstructured":"Tyshkevich, R.: Decomposition of graphical sequences and unigraphs. Discr. Math. 220, 201\u2013238 (2000)","journal-title":"Discr. Math."},{"key":"1_CR95","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1007\/BF01070234","volume":"23","author":"RI Tyshkevich","year":"1987","unstructured":"Tyshkevich, R.I., Chernyak, A.A., Chernyak, Z.A.: Graphs and degree sequences: a survey I. Cybernetics 23, 734\u2013745 (1987)","journal-title":"Cybernetics"},{"key":"1_CR96","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/BF01082602","volume":"24","author":"RI Tyshkevich","year":"1988","unstructured":"Tyshkevich, R.I., Chernyak, A.A., Chernyak, Z.A.: Graphs and degree sequences: a survey II. Cybernetics 24, 137\u2013152 (1988)","journal-title":"Cybernetics"},{"key":"1_CR97","doi-asserted-by":"crossref","unstructured":"Tyshkevich, R.I., Chernyak, A.A., Chernyak, Z.A.: Graphs and degree sequences: a survey III. Cybernetics 24, 539\u2013548 (1988)","DOI":"10.1007\/BF01255665"},{"key":"1_CR98","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1007\/BF01069217","volume":"17","author":"RI Tyshkevich","year":"1981","unstructured":"Tyshkevich, R.I., Mel\u2019nikov, O.I., Kotov, V.M.: Graphs and degree sequences: canonical decomposition. Cybernetics 17, 722\u2013727 (1981)","journal-title":"Cybernetics"},{"key":"1_CR99","unstructured":"Ulam, S.: A Collection of Mathematical Problems. Wiley, Hoboken (1960)"},{"issue":"1","key":"1_CR100","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":"1_CR101","first-page":"239","volume":"267","author":"N Wormald","year":"1999","unstructured":"Wormald, N.: Models of random regular graphs. Surveys Combin. 267, 239\u2013298 (1999)","journal-title":"Surveys Combin."},{"issue":"1\u20133","key":"1_CR102","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. Discr. Math. 105(1\u20133), 293\u2013303 (1992)","journal-title":"Discr. Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79987-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,4]],"date-time":"2023-02-04T14:03:12Z","timestamp":1675519392000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79987-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030799861","9783030799878"],"references-count":102,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79987-8_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"30 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ottawa, ON","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2021.eecs.uottawa.ca\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"107","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"36% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9.1","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The workshop was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}