{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T01:53:00Z","timestamp":1772502780078,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T00:00:00Z","timestamp":1681084800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T00:00:00Z","timestamp":1681084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE40-0032"],"award-info":[{"award-number":["ANR-18-CE40-0032"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE40-0032"],"award-info":[{"award-number":["ANR-18-CE40-0032"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100020955","name":"Sakura Science Exchange Program","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100020955","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100020955","name":"Sakura Science Exchange Program","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100020955","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100020955","name":"Sakura Science Exchange Program","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100020955","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"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP19K11814"],"award-info":[{"award-number":["JP19K11814"]}],"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":["JP18H05291"],"award-info":[{"award-number":["JP18H05291"]}],"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":["JP20K11692"],"award-info":[{"award-number":["JP20K11692"]}],"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"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20K11666"],"award-info":[{"award-number":["JP20K11666"]}],"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":["JP20H05794"],"award-info":[{"award-number":["JP20H05794"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JPMJCR18K3"],"award-info":[{"award-number":["JPMJCR18K3"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JPMJCR1401"],"award-info":[{"award-number":["JPMJCR1401"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JP19K20350"],"award-info":[{"award-number":["JP19K20350"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JP20H05793"],"award-info":[{"award-number":["JP20H05793"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,9]]},"DOI":"10.1007\/s00453-023-01117-z","type":"journal-article","created":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T11:02:31Z","timestamp":1681124551000},"page":"2779-2816","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Reconfiguration of Spanning Trees with Degree Constraints or Diameter Constraints"],"prefix":"10.1007","volume":"85","author":[{"given":"Nicolas","family":"Bousquet","sequence":"first","affiliation":[]},{"given":"Takehiro","family":"Ito","sequence":"additional","affiliation":[]},{"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[]},{"given":"Haruka","family":"Mizuta","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Ouvrard","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5212-0202","authenticated-orcid":false,"given":"Akira","family":"Suzuki","sequence":"additional","affiliation":[]},{"given":"Kunihiro","family":"Wasa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,10]]},"reference":[{"key":"1117_CR1","doi-asserted-by":"crossref","unstructured":"Barjon, M., Casteigts, A., Chaumette, S., Johnen, C., Neggaz, Y.M.: Maintaining a spanning forest in highly dynamic networks: the synchronous case. In: Marcos\u00a0K., Aguilera, L.Q., Marc S., (eds.) Principles of Distributed Systems, pp. 277\u2013292. Springer International Publishing, Cham (2014)","DOI":"10.1007\/978-3-319-14472-6_19"},{"key":"1117_CR2","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: 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), pp. 24:1\u201324:15 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.24","DOI":"10.4230\/LIPIcs.ESA.2020.24"},{"issue":"4","key":"1117_CR3","doi-asserted-by":"publisher","first-page":"1542","DOI":"10.1137\/120864271","volume":"42","author":"Sergio Cabello","year":"2013","unstructured":"Cabello, Sergio, Chambers, Erin W., Erickson, Jeff: Multiple-source shortest paths in embedded graphs. SIAM J. Comput. 42(4), 1542\u20131571 (2013). https:\/\/doi.org\/10.1137\/120864271","journal-title":"SIAM J. Comput."},{"key":"1117_CR4","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Strothmann, WB.: Bounded degree spanning trees. In: Rainer, B., Gerhard, W., (eds.) Algorithms \u2014 ESA \u201997, Vol. 1284 of LNCS, pp. 104\u2013117. Springer Berlin Heidelberg, Berlin Heidelberg (1997)","DOI":"10.1007\/3-540-63397-9_9"},{"issue":"3","key":"1117_CR5","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"Martin Furer","year":"1994","unstructured":"Furer, Martin, Raghavachari, Balaji: Approximating the minimum-degree steiner tree to within one of optimal. J. Algorithms 17(3), 409\u2013423 (1994). https:\/\/doi.org\/10.1006\/jagm.1994.1042","journal-title":"J. Algorithms"},{"key":"1117_CR6","doi-asserted-by":"publisher","unstructured":"Goemans, MX.: Minimum bounded degree spanning trees. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pp. 273\u2013282. IEEE Computer Society. https:\/\/doi.org\/10.1109\/FOCS.2006.48 (2006)","DOI":"10.1109\/FOCS.2006.48"},{"issue":"3","key":"1117_CR7","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0166-218X(03)00360-3","volume":"137","author":"R Hassin","year":"2004","unstructured":"Hassin, R., Levin, A.: Minimum restricted diameter spanning trees. Discret. Appl. Math. 137(3), 343\u2013357 (2004). https:\/\/doi.org\/10.1016\/S0166-218X(03)00360-3","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1117_CR8","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0020-0190(94)00183-Y","volume":"53","author":"Refael Hassin","year":"1995","unstructured":"Hassin, Refael, Tamir, Arie: On the minimum diameter spanning tree problem. Inf. Process. Lett. 53(2), 109\u2013111 (1995). https:\/\/doi.org\/10.1016\/0020-0190(94)00183-Y","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"1117_CR9","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","volume":"343","author":"Robert A Hearn","year":"2005","unstructured":"Hearn, Robert A., Demaine, Erik D.: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci. 343(1\u20132), 72\u201396 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.05.008","journal-title":"Theor. Comput. Sci."},{"key":"1117_CR10","doi-asserted-by":"publisher","unstructured":"van den Heuvel, J.: The complexity of change. In: Simon, R., Blackburn, S.G., Mark W. (eds.)Surveys in Combinatorics, Vol. 409 of London Mathematical Society Lecture Note Series, pp. 127\u2013160. Cambridge University Press (2013). https:\/\/doi.org\/10.1017\/CBO9781139506748.005","DOI":"10.1017\/CBO9781139506748.005"},{"key":"1117_CR11","doi-asserted-by":"publisher","unstructured":"Huang, S., Fu, AWC., Liu, R.: Minimum spanning trees in temporal graphs. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD \u201915, pp 419-430, New York, NY, USA, (2015). Association for Computing Machinery. https:\/\/doi.org\/10.1145\/2723372.2723717","DOI":"10.1145\/2723372.2723717"},{"issue":"3","key":"1117_CR12","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/PL00009225","volume":"22","author":"Giuseppe F Italiano","year":"1998","unstructured":"Italiano, Giuseppe F., Ramaswami, Rajiv: Maintaining spanning trees of small diameter. Algorithmica 22(3), 275\u2013304 (1998). https:\/\/doi.org\/10.1007\/PL00009225","journal-title":"Algorithmica"},{"issue":"12","key":"1117_CR13","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., Harvey, N.J.A., Papadimitriou, C.H., MarthaSideri, R., Uno, Y.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12), 1054\u20131065 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2010.12.005","journal-title":"Theor. Comput. Sci."},{"key":"1117_CR14","doi-asserted-by":"crossref","unstructured":"Karp, R.\u00a0M.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1117_CR15","doi-asserted-by":"publisher","unstructured":"Korte, B. H., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer-Verlag, New York, NY, (2012). https:\/\/doi.org\/10.1007\/978-3-642-24488-9","DOI":"10.1007\/978-3-642-24488-9"},{"key":"1117_CR16","doi-asserted-by":"publisher","unstructured":"Mizuta, H., Hatanaka, T., Ito, T., Zhou, X.: Reconfiguration of minimum steiner trees via vertex exchanges. In: 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, pp. 79:1\u201379:11, (2019). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.79","DOI":"10.4230\/LIPIcs.MFCS.2019.79"},{"issue":"4","key":"1117_CR17","doi-asserted-by":"publisher","first-page":"52","DOI":"10.3390\/a11040052","volume":"11","author":"Naomi Nishimura","year":"2018","unstructured":"Nishimura, Naomi: Introduction to reconfiguration. Algorithms 11(4), 52 (2018). https:\/\/doi.org\/10.3390\/a11040052","journal-title":"Algorithms"},{"key":"1117_CR18","unstructured":"Schrijver, A.: Combinatorial Optimization\u2014Polyhedra and Efficiency. Springer (2003)"},{"key":"1117_CR19","doi-asserted-by":"publisher","unstructured":"Singh, M., Lau, L. C.: Approximating minimum bounded degree spanning trees to within one of optimal. J. ACM, 62(1), (March 2015). https:\/\/doi.org\/10.1145\/2629366","DOI":"10.1145\/2629366"},{"issue":"4","key":"1117_CR20","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s00453-003-1056-z","volume":"38","author":"MJ Spriggs","year":"2004","unstructured":"Spriggs, M.J., Keil, J.M., Bespamyatnikh, S., Segal, M., Snoeyink, J.: Computing a $$(1+\\varepsilon )$$-approximate geometric minimum-diameter spanning tree. Algorithmica 38(4), 577\u2013589 (2004). https:\/\/doi.org\/10.1007\/s00453-003-1056-z","journal-title":"Algorithmica"},{"issue":"9","key":"1117_CR21","doi-asserted-by":"publisher","first-page":"140","DOI":"10.3390\/a11090140","volume":"11","author":"A Takaoka","year":"2018","unstructured":"Takaoka, A.: Complexity of Hamiltonian cycle reconfiguration. Algorithms 11(9), 140 (2018). https:\/\/doi.org\/10.3390\/a11090140","journal-title":"Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01117-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01117-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01117-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T15:03:53Z","timestamp":1695395033000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01117-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,10]]},"references-count":21,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1117"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01117-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,10]]},"assertion":[{"value":"29 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2023","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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}