{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T04:04:11Z","timestamp":1747541051050,"version":"3.40.5"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031929311","type":"print"},{"value":"9783031929328","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-92932-8_4","type":"book-chapter","created":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:17Z","timestamp":1747468037000},"page":"51-67","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computational Complexity of\u00a0Combinatorial Distance Matrix Realisation"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5377-9797","authenticated-orcid":false,"given":"David L.","family":"Fairbairn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7182-585X","authenticated-orcid":false,"given":"George B.","family":"Mertzios","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9630-7901","authenticated-orcid":false,"given":"Norbert","family":"Peyerimhoff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,18]]},"reference":[{"issue":"2","key":"4_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. Discret. Comput. Geom. 3(2), 103\u2013122 (1988)","journal-title":"Discret. Comput. Geom."},{"issue":"2","key":"4_CR2","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/3305218.3305232","volume":"46","author":"A Anirudh Sabnis","year":"2019","unstructured":"Anirudh Sabnis, A., Sitaraman, R.K., Towsley, D.: Occam: an optimization based approach to network inference. SIGMETRICS Perform. Eval. Rev. 46(2), 36\u201338 (2019)","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Atzmon, D., Bernardini, S., Fagnani, F., Fairbairn, D.: Exploiting geometric constraints in multi-agent pathfinding. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 33, no. 1, pp. 17\u201325 (2023)","DOI":"10.1609\/icaps.v33i1.27174"},{"issue":"3","key":"4_CR4","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":"4_CR5","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":"3","key":"4_CR6","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0001-8708(84)90029-X","volume":"53","author":"A Dress","year":"1984","unstructured":"Dress, A.: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces. Adv. Math. 53(3), 321\u2013402 (1984)","journal-title":"Adv. Math."},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"D\u00edaz, J., Diner, \u00d6.Y., Serna, M., Serra, O.: The multicolored graph realization problem. Discret. Appl. Math. 354, 146\u2013159 (2024). 18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2020)","DOI":"10.1016\/j.dam.2022.06.031"},{"issue":"1","key":"4_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(02)00404-6","volume":"148","author":"C Feremans","year":"2003","unstructured":"Feremans, C., Labb\u00e9, M., Laporte, G.: Generalized network design problems. Eur. J. Oper. Res. 148(1), 1\u201313 (2003)","journal-title":"Eur. J. Oper. Res."},{"key":"4_CR9","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. Q. Appl. Math. 22, 305\u2013317 (1965)","journal-title":"Q. Appl. Math."},{"key":"4_CR10","volume-title":"Discrete Tomography: Foundations, Algorithms, and Applications","author":"GT Herman","year":"2012","unstructured":"Herman, G.T., Kuba, A.: Discrete Tomography: Foundations, Algorithms, and Applications. Springer, New York City (2012)"},{"key":"4_CR11","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations (Proceedings of the Symposium, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pp. 85\u2013103. The IBM Research Symposia Series, Plenum, New York-London (1972)"},{"issue":"1","key":"4_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10458-022-09583-5","volume":"37","author":"N Klobas","year":"2023","unstructured":"Klobas, N., Mertzios, G.B., Molter, H., Niedermeier, R., Zschoche, P.: Interference-free walks in time: temporally disjoint paths. Auton. Agent. Multi-Agent Syst. 37(1), 1 (2023)","journal-title":"Auton. Agent. Multi-Agent Syst."},{"issue":"35","key":"4_CR13","doi-asserted-by":"publisher","first-page":"4482","DOI":"10.1016\/j.tcs.2011.04.013","volume":"412","author":"G Kortsarz","year":"2011","unstructured":"Kortsarz, G., Nutov, Z.: Approximating some network design problems with node costs. Theor. Comput. Sci. 412(35), 4482\u20134492 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR14","unstructured":"Lov\u00e1sz, L.: Coverings and coloring of hypergraphs. In: Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1973). Congress. Numer., vol.\u00a0VIII, pp. 3\u201312. Utilitas Math., Winnipeg, MB, USA (1973)"},{"key":"4_CR15","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"4_CR16","volume-title":"Phylogenetics, Oxford Lecture Series in Mathematics and its Applications","author":"C Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics, Oxford Lecture Series in Mathematics and its Applications, vol. 24. Oxford University Press, Oxford (2003)"},{"key":"4_CR17","unstructured":"Stern, R., et al.: Multi-agent pathfinding: definitions, variants, and benchmarks. In: Proceedings of the Symposium on Combinatorial Search (SoCS) (2019)"},{"issue":"3","key":"4_CR18","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/1008293.1008294","volume":"5","author":"L Stockmeyer","year":"1973","unstructured":"Stockmeyer, L.: Planar 3-colorability is polynomial complete. SIGACT News 5(3), 19\u201325 (1973)","journal-title":"SIGACT News"},{"issue":"6","key":"4_CR19","first-page":"90","volume":"20","author":"KA Zarecki\u012d","year":"1965","unstructured":"Zarecki\u012d, K.A.: Constructing a tree on the basis of a set of distances between the hanging vertices. Uspehi Mat. Nauk 20(6), 90\u201392 (1965)","journal-title":"Uspehi Mat. Nauk"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-92932-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T07:47:21Z","timestamp":1747468041000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-92932-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031929311","9783031929328"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-92932-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"18 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","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":"10 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/easyconferences.eu\/ciac2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}