{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T04:33:23Z","timestamp":1778301203511,"version":"3.51.4"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032118349","type":"print"},{"value":"9783032118356","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-11835-6_28","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:31:53Z","timestamp":1767313913000},"page":"390-404","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Realizing Temporal Transportation Trees"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7182-585X","authenticated-orcid":false,"given":"George\u00a0B.","family":"Mertzios","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4590-798X","authenticated-orcid":false,"given":"Hendrik","family":"Molter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7283-4982","authenticated-orcid":false,"given":"Nils","family":"Morawietz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5396-3749","authenticated-orcid":false,"given":"Paul\u00a0G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Arrighi, E., Gr\u00fcttemeier, N., Morawietz, N., Sommer, F., Wolf, P.: Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs. In: Proceedings of the 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pp. 283\u2013297 (2023)","DOI":"10.1007\/978-3-031-23101-8_19"},{"issue":"6","key":"28_CR2","doi-asserted-by":"publisher","first-page":"1321","DOI":"10.1109\/TPDS.2021.3104239","volume":"33","author":"J Augustine","year":"2022","unstructured":"Augustine, J., Choudhary, K., Cohen, A., Peleg, D., Sivasubramaniam, S., Sourav, S.: Distributed graph realizations. IEEE Trans. Parallel Distrib. Syst. 33(6), 1321\u20131337 (2022)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"28_CR3","doi-asserted-by":"publisher","first-page":"4745","DOI":"10.1103\/PhysRevLett.84.4745","volume":"84","author":"JR Banavar","year":"2000","unstructured":"Banavar, J.R., Colaiori, F., Flammini, A., Maritan, A., Rinaldo, A.: Topology of the fittest transportation network. Phys. Rev. Lett. 84, 4745\u20134748 (2000)","journal-title":"Phys. Rev. Lett."},{"issue":"4","key":"28_CR4","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. Discret. Math. 34(4), 2318\u20132337 (2020)","journal-title":"SIAM J. Discret. Math."},{"issue":"9","key":"28_CR5","doi-asserted-by":"publisher","first-page":"113483","DOI":"10.1016\/j.disc.2023.113483","volume":"346","author":"A Bar-Noy","year":"2023","unstructured":"Bar-Noy, A., Choudhary, K., Peleg, D., Rawitz, D.: Graph realizations: maximum degree in vertex neighborhoods. Discret. Math. 346(9), 113483 (2023)","journal-title":"Discret. Math."},{"issue":"3","key":"28_CR6","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":"28_CR7","doi-asserted-by":"publisher","first-page":"114810","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":"07","key":"28_CR8","doi-asserted-by":"publisher","first-page":"L07002","DOI":"10.1088\/1742-5468\/2006\/07\/L07002","volume":"2006","author":"M Barth\u00e9lemy","year":"2006","unstructured":"Barth\u00e9lemy, M., Flammini, A.: Optimal traffic networks. J. Stat. Mech. Theory Exp. 2006(07), L07002 (2006)","journal-title":"J. Stat. Mech. Theory Exp."},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Behzad, M., Simpson, J.E.: Eccentric sequences and eccentric sets in graphs. Discrete Math. 16(3), 187\u2013193 (1976)","DOI":"10.1016\/0012-365X(76)90098-4"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Bixby, R.E., Wagner, D.K.: An almost linear-time algorithm for graph realization. Math. Oper. Res. 13(1), 99\u2013123 (1988)","DOI":"10.1287\/moor.13.1.99"},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"088702","DOI":"10.1103\/PhysRevLett.98.088702","volume":"98","author":"S Bohn","year":"2007","unstructured":"Bohn, S., Magnasco, M.O.: Structure, scaling, and phase transition in the optimal transport network. Phys. Rev. Lett. 98, 088702 (2007)","journal-title":"Phys. Rev. Lett."},{"issue":"5","key":"28_CR12","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"Chaudhary, J., Molter, H., Zehavi, M.: Parameterized analysis of bribery in challenge the champ tournaments. In: Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pp. 2704\u20132712 (2024)","DOI":"10.1613\/jair.1.17239"},{"issue":"5","key":"28_CR14","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."},{"issue":"3","key":"28_CR15","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1006\/jcss.2001.1785","volume":"63","author":"F Chung","year":"2001","unstructured":"Chung, F., Garrett, M., Graham, R., 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":"28_CR16","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."},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"Dadush, D., Peikert, C., Vempala, S.: Enumerative lattice algorithms in any norm via $$M$$-ellipsoid coverings. In: Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 580\u2013589. IEEE (2011)","DOI":"10.1109\/FOCS.2011.31"},{"key":"28_CR18","first-page":"264","volume":"11","author":"P Erd\u00f6s","year":"1960","unstructured":"Erd\u00f6s, P., Gallai, T.: Graphs with prescribed degrees of vertices. Mat. Lapok 11, 264\u2013274 (1960)","journal-title":"Mat. Lapok"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"103534","DOI":"10.1016\/j.jcss.2024.103534","volume":"144","author":"T Erlebach","year":"2024","unstructured":"Erlebach, T., Morawietz, N., Spooner, J.T., Wolf, P.: A cop and robber game on edge-periodic temporal graphs. J. Comput. Syst. Sci. 144, 103534 (2024)","journal-title":"J. Comput. Syst. Sci."},{"key":"28_CR20","unstructured":"Erlebach, T., Morawietz, N., Wolf, P.: Parameterized algorithms for multi-label periodic temporal graph realization. In: Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND), pp. 12:1\u201312:16 (2024)"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"Erlebach, T., Spooner, J.T.: A game of cops and robbers on graphs with periodic edge-connectivity. In: Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM), pp. 64\u201375 (2020)","DOI":"10.1007\/978-3-030-38919-2_6"},{"issue":"1","key":"28_CR22","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. Discret. Math. 5(1), 25\u201353 (1992)","journal-title":"SIAM J. Discret. Math."},{"key":"28_CR23","unstructured":"Frank, A.: Connectivity augmentation problems in network design. In: Mathematical Programming: State of the Art 1994 (1994)"},{"key":"28_CR24","doi-asserted-by":"crossref","unstructured":"Frank, H., Chou, W.: Connectivity considerations in the design of survivable networks. IEEE Trans. Circ. Theor. 17(4), 486\u2013490 (1970)","DOI":"10.1109\/TCT.1970.1083185"},{"issue":"3","key":"28_CR25","doi-asserted-by":"publisher","first-page":"831","DOI":"10.2140\/pjm.1960.10.831","volume":"10","author":"DR Fulkerson","year":"1960","unstructured":"Fulkerson, D.R.: Zero-one matrices with zero trace. Pac. J. Math. 10(3), 831\u2013836 (1960)","journal-title":"Pac. J. Math."},{"key":"28_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.12.007","volume":"665","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A., Mertzios, G.B.: Graph editing to a given degree sequence. Theoret. Comput. Sci. 665, 1\u201312 (2017)","journal-title":"Theoret. Comput. Sci."},{"key":"28_CR27","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C., Trenk, A.N.: Tolerance Graphs. Cambridge Studies in Advanced Mathematics. Cambridge University Press (2004)","DOI":"10.1017\/CBO9780511542985"},{"key":"28_CR28","doi-asserted-by":"crossref","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9(4), 551\u2013570 (1961)","DOI":"10.1137\/0109047"},{"key":"28_CR29","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Monma, C.L., Stoer, M.: Design of survivable networks. Handbooks Oper. Res. Manage. Sci. 7, 617\u2013672 (1995)","DOI":"10.1016\/S0927-0507(05)80127-6"},{"key":"28_CR30","doi-asserted-by":"crossref","unstructured":"Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph.\u00a0I. J. Soc. Ind. Appl. Math. 10(3), 496\u2013506 (1962)","DOI":"10.1137\/0110037"},{"key":"28_CR31","doi-asserted-by":"crossref","unstructured":"Hakimi, S.L., Yau, S.S.: Distance matrix of a graph and its realizability. Quart. Appl. Math. 22(4), 305\u2013317 (1965)","DOI":"10.1090\/qam\/184873"},{"issue":"18","key":"28_CR32","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. Discret. Math. 309(18), 5703\u20135713 (2009)","journal-title":"Discret. Math."},{"key":"28_CR33","doi-asserted-by":"crossref","unstructured":"Holme, P., Saram\u00e4ki, J.: Temporal Network Theory, vol.\u00a02. Springer (2019)","DOI":"10.1007\/978-3-030-23495-9"},{"issue":"4","key":"28_CR34","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1006\/jcss.2002.1829","volume":"64","author":"D Kempe","year":"2002","unstructured":"Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820\u2013842 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"28_CR35","unstructured":"Klobas, N., Mertzios, G.B., Molter, H., Spirakis, P.G.: Temporal graph realization from fastest paths. In: Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND), pp. 16:1\u201316:18 (2024)"},{"key":"28_CR36","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"28_CR37","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, 287\u2013293 (1975)","journal-title":"Period. Math. Hung."},{"key":"28_CR38","unstructured":"McConnell, R.M., Spinrad, J.P.: Construction of probe interval models. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 866\u2013875 (2002)"},{"key":"28_CR39","doi-asserted-by":"crossref","unstructured":"McMorris, F.R., Wang, C., Zhang, P.: On probe interval graphs. Discrete Appl. Math. 88(1), 315\u2013324 (1998). Computational Molecular Biology DAM - CMB Series","DOI":"10.1016\/S0166-218X(98)00077-8"},{"key":"28_CR40","unstructured":"Mertzios, G.B., Molter, H., Morawietz, N., Spirakis, P.G.: Realizing temporal transportation trees. CoRR, abs\/2403.18513, (2025). https:\/\/arxiv.org\/abs\/2403.18513"},{"issue":"2","key":"28_CR41","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1145\/3156693","volume":"61","author":"O Michail","year":"2018","unstructured":"Michail, O., Spirakis, P.G.: Elements of the theory of dynamic networks. Commun. ACM 61(2), 72\u201372 (2018)","journal-title":"Commun. ACM"},{"key":"28_CR42","unstructured":"Morawietz, N., Rehs, C., Weller, M.: A timecop\u2019s work is harder than you think. In: Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), vol. 170, pp. 71:1\u201371:14 (2020)"},{"key":"28_CR43","unstructured":"Morawietz, N., Wolf, P.: A timecop\u2019s chase around the table. In: Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS) (2021)"},{"key":"28_CR44","doi-asserted-by":"crossref","unstructured":"Nicosia, V., Tang, J., Mascolo, C., Musolesi, M., Russo, G., Latora, V.: Graph metrics for temporal networks. In: Temporal Networks, Springer (2013)","DOI":"10.1007\/978-3-642-36461-7_2"},{"key":"28_CR45","doi-asserted-by":"crossref","unstructured":"Patrinos, A.N., Louis Hakimi, S.: The distance matrix of a graph and its tree realization. Quart. Appl. Math. 30, 255\u2013269 (1972)","DOI":"10.1090\/qam\/414405"},{"key":"28_CR46","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":"28_CR47","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol.\u00a024. Springer (2003)"},{"key":"28_CR48","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: Proceedings of the 1993 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 2545\u20132548 (1993)","DOI":"10.1109\/ISCAS.1993.693210"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-11835-6_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:31:56Z","timestamp":1767313916000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-11835-6_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032118349","9783032118356"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-11835-6_28","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":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Otzenhausen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo.uni-trier.de\/wg2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}