{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T16:52:08Z","timestamp":1770051128179,"version":"3.49.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T00:00:00Z","timestamp":1766361600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T00:00:00Z","timestamp":1766361600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18H04091"],"award-info":[{"award-number":["JP18H04091"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H05795"],"award-info":[{"award-number":["JP20H05795"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H05795"],"award-info":[{"award-number":["JP20H05795"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H05793"],"award-info":[{"award-number":["JP20H05793"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H05795"],"award-info":[{"award-number":["JP20H05795"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H05795"],"award-info":[{"award-number":["JP20H05795"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18H04091"],"award-info":[{"award-number":["JP18H04091"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,2]]},"DOI":"10.1007\/s00453-025-01365-1","type":"journal-article","created":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T03:52:01Z","timestamp":1766375521000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Reconfiguration of Time-Respecting Arborescences"],"prefix":"10.1007","volume":"88","author":[{"given":"Takehiro","family":"Ito","sequence":"first","affiliation":[]},{"given":"Yuni","family":"Iwamasa","sequence":"additional","affiliation":[]},{"given":"Naoyuki","family":"Kamiyama","sequence":"additional","affiliation":[]},{"given":"Yasuaki","family":"Kobayashi","sequence":"additional","affiliation":[]},{"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[]},{"given":"Shun-ichi","family":"Maezawa","sequence":"additional","affiliation":[]},{"given":"Akira","family":"Suzuki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,22]]},"reference":[{"key":"1365_CR1","first-page":"1396","volume":"14","author":"Y-J Chu","year":"1965","unstructured":"Chu, Y.-J.: On the shortest arborescence of a directed graph. Sci. Sinica 14, 1396\u20131400 (1965)","journal-title":"Sci. Sinica"},{"issue":"4","key":"1365_CR2","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071b.032","volume":"71","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. natl. Bureau Stand. B 71(4), 233\u2013240 (1967). https:\/\/doi.org\/10.6028\/jres.071b.032","journal-title":"J. Res. natl. Bureau Stand. B"},{"issue":"1","key":"1365_CR3","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/S0304-3975(02)00888-5","volume":"301","author":"L Georgiadis","year":"2003","unstructured":"Georgiadis, L.: Arborescence optimization problems solvable by Edmonds\u2019 algorithm. Theoret. Comput. Sci. 301(1), 427\u2013437 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00888-5","journal-title":"Theoret. Comput. Sci."},{"key":"1365_CR4","first-page":"91","volume-title":"Combinatorial Algorithms","author":"J Edmonds","year":"1973","unstructured":"Edmonds, J.: Edge-disjoint branchings. In: Rustin, R. (ed.) Combinatorial Algorithms, pp. 91\u201396. Academic Press, New York, NY (1973)"},{"issue":"4","key":"1365_CR5","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). https:\/\/doi.org\/10.1006\/jcss.2002.1829","journal-title":"J. Comput. Syst. Sci."},{"issue":"12\u201314","key":"1365_CR6","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito, T., Demaine, E.D., Harvey, N.J.A., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theoret. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2010.12.005","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1365_CR7","doi-asserted-by":"publisher","first-page":"52","DOI":"10.3390\/a11040052","volume":"11","author":"N Nishimura","year":"2018","unstructured":"Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4), 52 (2018). https:\/\/doi.org\/10.3390\/a11040052","journal-title":"Introduction to reconfiguration. Algorithms"},{"issue":"1","key":"1365_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J Edmonds","year":"1971","unstructured":"Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1(1), 127\u2013136 (1971). https:\/\/doi.org\/10.1007\/BF01584082","journal-title":"Math. Program."},{"key":"1365_CR9","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.tcs.2022.12.007","volume":"943","author":"T Ito","year":"2023","unstructured":"Ito, T., Iwamasa, Y., Kobayashi, Y., Nakahata, Y., Otachi, Y., Wasa, K.: Reconfiguring (non-spanning) arborescences. Theor. Comput. Sci. 943, 131\u2013141 (2023). https:\/\/doi.org\/10.1016\/j.tcs.2022.12.007","journal-title":"Theor. Comput. Sci."},{"key":"1365_CR10","doi-asserted-by":"publisher","unstructured":"Bousquet, N., Ito, T., Kobayashi, Y., Mizuta, H., Ouvrard, P., Suzuki, A., Wasa, K.: Reconfiguration of spanning trees with many or few leaves. In: Grandoni, F., Herman, G., Sanders, P. (eds.) Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics, vol. 173, pp. 24\u201312415. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.24","DOI":"10.4230\/LIPIcs.ESA.2020.24"},{"key":"1365_CR11","doi-asserted-by":"publisher","unstructured":"Bousquet, N., Ito, T., Kobayashi, Y., Mizuta, H., Ouvrard, P., Suzuki, A., Wasa, K.: Reconfiguration of spanning trees with degree constraint or diameter constraint. In: Berenbrink, P., Monmege, B. (eds.) Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics, vol. 219, pp. 15\u201311521. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2022.15","DOI":"10.4230\/LIPIcs.STACS.2022.15"},{"key":"1365_CR12","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/j.tcs.2019.09.018","volume":"806","author":"T Hanaka","year":"2020","unstructured":"Hanaka, T., Ito, T., Mizuta, H., Moore, B., Nishimura, N., Subramanya, V., Suzuki, A., Vaidyanathan, K.: Reconfiguring spanning and induced subgraphs. Theor. Comput. Sci. 806, 553\u2013566 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2019.09.018","journal-title":"Theor. Comput. Sci."},{"key":"1365_CR13","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.tcs.2017.10.031","volume":"748","author":"MD Biasi","year":"2018","unstructured":"Biasi, M.D., Ophelders, T.: The complexity of snake and undirected NCL variants. Theor. Comput. Sci. 748, 55\u201365 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2017.10.031","journal-title":"Theor. Comput. Sci."},{"key":"1365_CR14","doi-asserted-by":"publisher","unstructured":"Demaine, E.D., Eppstein, D., Hesterberg, A., Jain, K., Lubiw, A., Uehara, R., Uno, Y.: Reconfiguring undirected paths. In: Friggstad, Z., Sack, J., Salavatipour, M.R. (eds.) Proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS 2019). Lecture Notes in Computer Science, vol. 11646, pp. 353\u2013365. Springer, Cham, Switzerland (2019). https:\/\/doi.org\/10.1007\/978-3-030-24766-9_26","DOI":"10.1007\/978-3-030-24766-9_26"},{"key":"1365_CR15","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1613\/jair.1.11864","volume":"69","author":"S Gupta","year":"2020","unstructured":"Gupta, S., Sa\u2019ar, G., Zehavi, M.: The parameterized complexity of motion planning for snake-like robots. J. Artif. Intell. Res. 69, 191\u2013229 (2020). https:\/\/doi.org\/10.1613\/jair.1.11864","journal-title":"J. Artif. Intell. Res."},{"issue":"2","key":"1365_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoret. Comput. Sci. 10(2), 111\u2013121 (1980). https:\/\/doi.org\/10.1016\/0304-3975(80)90009-2","journal-title":"Theoret. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01365-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01365-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01365-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T05:11:51Z","timestamp":1770009111000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01365-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,22]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["1365"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01365-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,22]]},"assertion":[{"value":"16 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"15"}}