{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:21:01Z","timestamp":1740122461215,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,4,27]],"date-time":"2018-04-27T00:00:00Z","timestamp":1524787200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,4,27]],"date-time":"2018-04-27T00:00:00Z","timestamp":1524787200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP16K00004"],"award-info":[{"award-number":["JP16K00004"]}],"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":["JPMJCR1402"],"award-info":[{"award-number":["JPMJCR1402"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009024","name":"Exploratory Research for Advanced Technology","doi-asserted-by":"publisher","award":["JPMJER1305"],"award-info":[{"award-number":["JPMJER1305"]}],"id":[{"id":"10.13039\/501100009024","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K00028"],"award-info":[{"award-number":["JP17K00028"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009023","name":"Precursory Research for Embryonic Science and Technology","doi-asserted-by":"publisher","award":["JPMJPR14E1"],"award-info":[{"award-number":["JPMJPR14E1"]}],"id":[{"id":"10.13039\/501100009023","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009024","name":"Exploratory Research for Advanced Technology","doi-asserted-by":"publisher","award":["JPMJER1305"],"award-info":[{"award-number":["JPMJER1305"]}],"id":[{"id":"10.13039\/501100009024","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP16K16010","JP16H03118"],"award-info":[{"award-number":["JP16K16010","JP16H03118"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Kayamori Foundation of Information Science Advancement"},{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JPMJCR1402"],"award-info":[{"award-number":["JPMJCR1402"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP24106005","JP24700008"],"award-info":[{"award-number":["JP24106005","JP24700008"]}],"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":["JP24220003","JP15K00009"],"award-info":[{"award-number":["JP24220003","JP15K00009"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s10878-018-0289-3","type":"journal-article","created":{"date-parts":[[2018,4,27]],"date-time":"2018-04-27T09:49:41Z","timestamp":1524822581000},"page":"454-464","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Reconfiguration of maximum-weight b-matchings in a graph"],"prefix":"10.1007","volume":"37","author":[{"given":"Takehiro","family":"Ito","sequence":"first","affiliation":[]},{"given":"Naonori","family":"Kakimura","sequence":"additional","affiliation":[]},{"given":"Naoyuki","family":"Kamiyama","sequence":"additional","affiliation":[]},{"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[]},{"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,27]]},"reference":[{"key":"289_CR1","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/s10878-012-9490-y","volume":"27","author":"M Bonamy","year":"2014","unstructured":"Bonamy M, Johnson M, Lignos I, Patel V, Paulusma D (2014) Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. J Comb Optim 27:132\u2013143","journal-title":"J Comb Optim"},{"key":"289_CR2","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.dam.2016.05.024","volume":"231","author":"P Bonsma","year":"2017","unstructured":"Bonsma P (2017) Rerouting shortest paths in planar graphs. Discrete Appl Math 231:95\u2013112","journal-title":"Discrete Appl Math"},{"key":"289_CR3","doi-asserted-by":"publisher","first-page":"5215","DOI":"10.1016\/j.tcs.2009.08.023","volume":"410","author":"P Bonsma","year":"2009","unstructured":"Bonsma P, Cereceda L (2009) Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor Comput Sci 410:5215\u20135226","journal-title":"Theor Comput Sci"},{"key":"289_CR4","doi-asserted-by":"crossref","unstructured":"Bonsma P, Kami\u0144ski M, Wrochna M (2014) Reconfiguring independent sets in claw-free graphs. In: Proceedings of the 14th Scandinavian symposium and workshops on algorithm theory (SWAT 2014). Lecture notes in computer science, vol 8503, pp 86\u201397","DOI":"10.1007\/978-3-319-08404-6_8"},{"key":"289_CR5","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.tcs.2015.07.037","volume":"600","author":"ED Demaine","year":"2015","unstructured":"Demaine ED, Demaine ML, Fox-Epstein E, Hoang DA, Ito T, Ono H, Otachi Y, Uehara R, Yamada T (2015) Linear-time algorithm for sliding tokens on trees. Theor Comput Sci 600:132\u2013142","journal-title":"Theor Comput Sci"},{"key":"289_CR6","doi-asserted-by":"publisher","first-page":"2330","DOI":"10.1137\/07070440X","volume":"38","author":"P Gopalan","year":"2009","unstructured":"Gopalan P, Kolaitis PG, Maneva EN, Papadimitriou CH (2009) The connectivity of Boolean satisfiability: computational and structural dichotomies. SIAM J Comput 38:2330\u20132355","journal-title":"SIAM J Comput"},{"key":"289_CR7","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1007\/s00373-013-1302-3","volume":"30","author":"R Haas","year":"2014","unstructured":"Haas R, Seyffarth K (2014) The $$k$$-dominating graph. Graphs Comb 30:609\u2013617","journal-title":"Graphs Comb"},{"key":"289_CR8","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2016.08.016","volume":"651","author":"A Haddadan","year":"2016","unstructured":"Haddadan A, Ito T, Mouawad AE, Nishimura N, Ono H, Suzuki A, Tebbal Y (2016) The complexity of dominating set reconfiguration. Theor Comput Sci 651:37\u201349","journal-title":"Theor Comput Sci"},{"key":"289_CR9","doi-asserted-by":"crossref","unstructured":"Hatanaka T, Ito T, Zhou X (2015) The list coloring reconfiguration problem for bounded pathwidth graphs. IEICE Trans Fundam Electron Commun Comput Sci E98-A:1168\u20131178","DOI":"10.1587\/transfun.E98.A.1168"},{"key":"289_CR10","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 ED, Harvey NJA, Papadimitriou CH, Sideri M, Uehara R, Uno Y (2011) On the complexity of reconfiguration problems. Theor Comput Sci 412:1054\u20131065","journal-title":"Theor Comput Sci"},{"key":"289_CR11","doi-asserted-by":"crossref","unstructured":"Ito T, Ono H, and Otachi Y (2015) Reconfiguration of cliques in a graph. In: Proceedings of the 12th annual conference on theory and applications of models of computation (TAMC\u00a02015), Lecture notes in computer science, vol 9076, pp 212\u2013223","DOI":"10.1007\/978-3-319-17142-5_19"},{"key":"289_CR12","doi-asserted-by":"crossref","unstructured":"Ito T, Nooka H, Zhou X (2016) Reconfiguration of vertex covers in a graph. IEICE Trans Inf Syst E99-D:598\u2013606","DOI":"10.1587\/transinf.2015FCP0010"},{"key":"289_CR13","doi-asserted-by":"crossref","unstructured":"Ito T, Kakimura N, Kamiyama N, Kobayashi Y, Okamoto Y (2017) Reconfiguration of maximum-weight $$b$$-matchings in a graph. In: Proceedings of the 23rd annual international computing and combinatorics conference (COCOON 2017). Lecture notes in computer science, vol 10392, pp 287\u2013296","DOI":"10.1007\/978-3-319-62389-4_24"},{"key":"289_CR14","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.tcs.2012.03.004","volume":"439","author":"M Kami\u0144ski","year":"2012","unstructured":"Kami\u0144ski M, Medvedev P, Milani\u010d M (2012) Complexity of independent set reconfigurability problems. Theor Comput Sci 439:9\u201315","journal-title":"Theor Comput Sci"},{"key":"289_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial optimization: theory and algorithms","author":"B Korte","year":"2012","unstructured":"Korte B, Vygen J (2012) Combinatorial optimization: theory and algorithms, 5th edn. Springer, Berlin","edition":"5"},{"key":"289_CR16","doi-asserted-by":"publisher","first-page":"4613","DOI":"10.1016\/j.tcs.2011.04.041","volume":"412","author":"K Makino","year":"2011","unstructured":"Makino K, Tamaki S, Yamamoto M (2011) An exact algorithm for the Boolean connectivity problem for $$k$$-CNF. Theor Comput Sci 412:4613\u20134618","journal-title":"Theor Comput Sci"},{"key":"289_CR17","doi-asserted-by":"crossref","unstructured":"Mizuta H, Ito T, Zhou X (2017) Reconfiguration of Steiner trees in an unweighted graph. IEICE Trans Fundam Electron Commun Comput Sci E100-A(7):1532\u20131540","DOI":"10.1587\/transfun.E100.A.1532"},{"key":"289_CR18","doi-asserted-by":"crossref","unstructured":"Mouawad AE, Nishimura N, Raman V (2014) Vertex cover reconfiguration and beyond. In: Proceedings of the 25th international symposium on algorithms and computation (ISAAC 2014). Lecture notes in computer science, vol 8889, pp 452\u2013463","DOI":"10.1007\/978-3-319-13075-0_36"},{"key":"289_CR19","doi-asserted-by":"publisher","first-page":"2185","DOI":"10.1137\/16M1065288","volume":"31","author":"AE Mouawad","year":"2017","unstructured":"Mouawad AE, Nishimura N, Pathak V, Raman V (2017) Shortest reconfiguration paths in the solution space of Boolean formulas. SIAM J Discrete Math 31:2185\u20132200","journal-title":"SIAM J Discrete Math"},{"key":"289_CR20","doi-asserted-by":"crossref","unstructured":"M\u00fchlenthaler M (2015) Degree-constrained subgraph reconfiguration is in P. In: Proceedings of the 40th international symposium on mathematical foundations of computer science (MFCS 2015). Lecture notes in computer science, vol 9235, pp 505\u2013516","DOI":"10.1007\/978-3-662-48054-0_42"},{"key":"289_CR21","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Springer, Berlin"},{"key":"289_CR22","unstructured":"van den Heuvel J (2013) The complexity of change. In: Surveys in combinatorics 2013. London Mathematical Society lecture notes series, vol 409, pp 127\u2013160"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0289-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0289-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0289-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T12:49:01Z","timestamp":1589719741000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0289-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,27]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["289"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0289-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2018,4,27]]},"assertion":[{"value":"27 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}