{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T20:07:43Z","timestamp":1773778063301,"version":"3.50.1"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031332708","type":"print"},{"value":"9783031332715","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-33271-5_12","type":"book-chapter","created":{"date-parts":[[2023,5,22]],"date-time":"2023-05-22T17:03:04Z","timestamp":1684774984000},"page":"167-183","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["ZDD-Based Algorithmic Framework for\u00a0Solving Shortest Reconfiguration Problems"],"prefix":"10.1007","author":[{"given":"Takehiro","family":"Ito","sequence":"first","affiliation":[]},{"given":"Jun","family":"Kawahara","sequence":"additional","affiliation":[]},{"given":"Yu","family":"Nakahata","sequence":"additional","affiliation":[]},{"given":"Takehide","family":"Soh","sequence":"additional","affiliation":[]},{"given":"Akira","family":"Suzuki","sequence":"additional","affiliation":[]},{"given":"Junichi","family":"Teruyama","sequence":"additional","affiliation":[]},{"given":"Takahisa","family":"Toda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,23]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","unstructured":"Akitaya, H.A., et al.: Reconfiguration of connected graph partitions. J. Graph Theory 102(1), 35\u201366 (2023). https:\/\/doi.org\/10.1002\/jgt.22856. https:\/\/onlinelibrary.wiley.com\/doi\/abs\/10.1002\/jgt.22856","DOI":"10.1002\/jgt.22856"},{"issue":"50","key":"12_CR2","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.: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoret. Comput. Sci. 410(50), 5215\u20135226 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.08.023","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR3","doi-asserted-by":"publisher","unstructured":"Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C-35(8), 677\u2013691 (1986). https:\/\/doi.org\/10.1109\/TC.1986.1676819","DOI":"10.1109\/TC.1986.1676819"},{"issue":"4","key":"12_CR4","doi-asserted-by":"publisher","first-page":"2271","DOI":"10.1287\/ijoc.2022.1170","volume":"34","author":"MP Castro","year":"2022","unstructured":"Castro, M.P., Cire, A.A., Beck, J.C.: Decision diagrams for discrete optimization: a survey of recent advances. INFORMS J. Comput. 34(4), 2271\u20132295 (2022). https:\/\/doi.org\/10.1287\/ijoc.2022.1170","journal-title":"INFORMS J. Comput."},{"key":"12_CR5","doi-asserted-by":"publisher","unstructured":"Censor-Hillel, K., Rabie, M.: Distributed reconfiguration of maximal independent sets. J. Comput. Syst. Sci. 112, 85\u201396 (2020). https:\/\/doi.org\/10.1016\/j.jcss.2020.03.003. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000020300349","DOI":"10.1016\/j.jcss.2020.03.003"},{"issue":"5\u20136","key":"12_CR6","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1016\/j.disc.2007.07.028","volume":"308","author":"L Cereceda","year":"2008","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Connectedness of the graph of vertex-colourings. Discrete Math. 308(5\u20136), 913\u2013919 (2008). https:\/\/doi.org\/10.1016\/j.disc.2007.07.028","journal-title":"Discrete Math."},{"key":"12_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/3-540-45657-0_29","volume-title":"Computer Aided Verification","author":"A Cimatti","year":"2002","unstructured":"Cimatti, A., et al.: NuSMV 2: an OpenSource tool for symbolic model checking. In: Brinksma, E., Larsen, K.G. (eds.) CAV 2002. LNCS, vol. 2404, pp. 359\u2013364. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45657-0_29"},{"key":"12_CR8","doi-asserted-by":"publisher","unstructured":"Coudert, O.: Solving graph optimization problems with ZBDDs. In: Proceedings European Design and Test Conference, ED & TC 1997, pp. 224\u2013228 (1997). https:\/\/doi.org\/10.1109\/EDTC.1997.582363","DOI":"10.1109\/EDTC.1997.582363"},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1080\/2330443X.2020.1791773","volume":"7","author":"B Fifield","year":"2020","unstructured":"Fifield, B., Imai, K., Kawahara, J., Kenny, C.T.: The essential role of empirical validation in legislative redistricting simulation. Stat. Public Policy 7(1), 52\u201368 (2020). https:\/\/doi.org\/10.1080\/2330443X.2020.1791773","journal-title":"Stat. Public Policy"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BFb0030837","volume-title":"Computing and Combinatorics","author":"K Hayase","year":"1995","unstructured":"Hayase, K., Sadakane, K., Tani, S.: Output-size sensitiveness of OBDD construction through maximal independent set problem. In: Du, D.-Z., Li, M. (eds.) COCOON 1995. LNCS, vol. 959, pp. 229\u2013234. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/BFb0030837"},{"key":"12_CR11","doi-asserted-by":"publisher","unstructured":"van den Heuvel, J.: The complexity of change. In: Blackburn, S.R., Gerke, S., Wildon, M. (eds.) Surveys in Combinatorics 2013, London Mathematical Society Lecture No te Series, vol.\u00a0409, pp. 127\u2013160. Cambridge University Press, Cambridge (2013). https:\/\/doi.org\/10.1017\/CBO9781139506748.005","DOI":"10.1017\/CBO9781139506748.005"},{"issue":"1","key":"12_CR12","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1109\/TSG.2013.2288976","volume":"5","author":"T Inoue","year":"2014","unstructured":"Inoue, T., et al.: Distribution loss minimization with guaranteed error bound. IEEE Trans. Smart Grid 5(1), 102\u2013111 (2014). https:\/\/doi.org\/10.1109\/TSG.2013.2288976","journal-title":"IEEE Trans. Smart Grid"},{"issue":"12\u201314","key":"12_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.: 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."},{"key":"12_CR14","unstructured":"Iwashita, H., Minato, S.: Efficient top-down ZDD construction techniques using recursive specifications. TCS Technical reports TCS-TR-A-13-69 (2013)"},{"key":"12_CR15","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.: Complexity of independent set reconfigurability problems. Theoret. Comput. Sci. 439, 9\u201315 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.03.004","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR16","doi-asserted-by":"publisher","unstructured":"Kawahara, J., Inoue, T., Iwashita, H., Minato, S.: Frontier-based search for enumerating all constrained subgraphs with compressed representation. IEICE Trans. Fund. Electron. Commun. Comput. Sci. E100-A(9), 1773\u20131784 (2017). https:\/\/doi.org\/10.1587\/transfun.E100.A.1773","DOI":"10.1587\/transfun.E100.A.1773"},{"key":"12_CR17","doi-asserted-by":"publisher","unstructured":"Kawahara, J., Saitoh, T., Suzuki, H., Yoshinaka, R.: Solving the longest oneway-ticket problem and enumerating letter graphs by augmenting the two representative approaches with ZDDs. In: Proceedings of the Computational Intelligence in Information Systems Conference (CIIS 2016), vol. 532, pp. 294\u2013305 (2016). https:\/\/doi.org\/10.1007\/978-3-319-48517-1_26","DOI":"10.1007\/978-3-319-48517-1_26"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-030-34029-2_9","volume-title":"Analysis of Experimental Algorithms","author":"J Kawahara","year":"2019","unstructured":"Kawahara, J., Saitoh, T., Suzuki, H., Yoshinaka, R.: Colorful frontier-based search: implicit enumeration of chordal and interval subgraphs. In: Kotsireas, I., Pardalos, P., Parsopoulos, K.E., Souravlias, D., Tsokas, A. (eds.) SEA 2019. LNCS, vol. 11544, pp. 125\u2013141. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-34029-2_9"},{"key":"12_CR19","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1, 1st edn. Addison-Wesley Professional (2011)"},{"key":"12_CR20","doi-asserted-by":"publisher","unstructured":"Minato, S.: Zero-suppressed BDDs for set manipulation in combinatorial problems. In: Proceedings of the 30th ACM\/IEEE Design Automation Conference, pp. 272\u2013277 (1993). https:\/\/doi.org\/10.1145\/157485.164890","DOI":"10.1145\/157485.164890"},{"key":"12_CR21","doi-asserted-by":"publisher","unstructured":"Mizuta, H., Ito, T., Zhou, X.: Reconfiguration of steiner trees in an unweighted graph. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 100-A(7), 1532\u20131540 (2017). https:\/\/doi.org\/10.1587\/transfun.E100.A.1532","DOI":"10.1587\/transfun.E100.A.1532"},{"key":"12_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/978-3-030-39881-1_18","volume-title":"WALCOM: Algorithms and Computation","author":"Yu Nakahata","year":"2020","unstructured":"Nakahata, Yu., Kawahara, J., Horiyama, T., Minato, S.: Implicit enumeration of topological-minor-embeddings and its application to planar subgraph enumeration. In: Rahman, M.S., Sadakane, K., Sung, W.-K. (eds.) WALCOM 2020. LNCS, vol. 12049, pp. 211\u2013222. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-39881-1_18"},{"issue":"4","key":"12_CR23","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":"Algorithms"},{"key":"12_CR24","doi-asserted-by":"publisher","unstructured":"Sekine, K., Imai, H., Tani, S.: Computing the Tutte polynomial of a graph of moderate size. In: Proceedings of the 6th International Symposium on Algorithms and Computation, pp. 224\u2013233 (1995). https:\/\/doi.org\/10.1007\/BFb0015427","DOI":"10.1007\/BFb0015427"},{"key":"12_CR25","doi-asserted-by":"publisher","unstructured":"Soh, T., Okamoto, Y., Ito, T.: Core challenge 2022: solver and graph descriptions. CoRR abs\/2208.02495 (2022). https:\/\/doi.org\/10.48550\/arXiv.2208.02495","DOI":"10.48550\/arXiv.2208.02495"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Speck, D., Mattm\u00fcller, R., Nebel, B.: Symbolic top-k planning. In: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, 7\u201312 February 2020, pp. 9967\u20139974. AAAI Press (2020). https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/6552","DOI":"10.1609\/aaai.v34i06.6552"},{"key":"12_CR27","unstructured":"Turau, V., Weyer, C.: Finding shortest reconfigurations sequences of independent sets. In: Core Challenge 2022: Solver and Graph Descriptions, pp. 3\u201314 (2022)"}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-33271-5_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,22]],"date-time":"2023-05-22T17:04:52Z","timestamp":1684775092000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-33271-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031332708","9783031332715"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-33271-5_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"23 May 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nice","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 May 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/cpaior2023","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"71","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}