{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T14:19:19Z","timestamp":1772893159365,"version":"3.50.1"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031270505","type":"print"},{"value":"9783031270512","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-27051-2_22","type":"book-chapter","created":{"date-parts":[[2023,3,13]],"date-time":"2023-03-13T00:03:35Z","timestamp":1678665815000},"page":"254-266","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the\u00a0Complexity of\u00a0Distance-d Independent Set Reconfiguration"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8635-8462","authenticated-orcid":false,"given":"Duc A.","family":"Hoang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,13]]},"reference":[{"key":"22_CR1","first-page":"41","volume":"144","author":"G Agnarsson","year":"2000","unstructured":"Agnarsson, G., Greenlaw, R., Halld\u00f3rsson, M.M.: On powers of chordal graphs and their colorings. Congr. Numer. 144, 41\u201365 (2000)","journal-title":"Congr. Numer."},{"issue":"2","key":"22_CR2","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1017\/S1446788700025696","volume":"35","author":"R Balakrishnan","year":"1983","unstructured":"Balakrishnan, R., Paulraja, P.: Powers of chordal graphs. J. Aust. Math. Soc. 35(2), 211\u2013217 (1983). https:\/\/doi.org\/10.1017\/S1446788700025696","journal-title":"J. Aust. Math. Soc."},{"issue":"4","key":"22_CR3","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/s00224-020-09967-8","volume":"65","author":"R Belmonte","year":"2020","unstructured":"Belmonte, R., Kim, E.J., Lampis, M., Mitsou, V., Otachi, Y., Sikora, F.: Token sliding on split graphs. Theory Comput. Syst. 65(4), 662\u2013686 (2020). https:\/\/doi.org\/10.1007\/s00224-020-09967-8","journal-title":"Theory Comput. Syst."},{"key":"22_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-319-68705-6_10","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Bonamy","year":"2017","unstructured":"Bonamy, M., Bousquet, N.: Token sliding on chordal graphs. In: Bodlaender, H.L., Woeginger, G.J. (eds.) WG 2017. LNCS, vol. 10520, pp. 127\u2013139. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-68705-6_10"},{"issue":"2","key":"22_CR5","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1002\/jgt.21992","volume":"83","author":"PS Bonsma","year":"2016","unstructured":"Bonsma, P.S.: Independent set reconfiguration in cographs and their generalizations. J. Graph Theory 83(2), 164\u2013195 (2016). https:\/\/doi.org\/10.1002\/jgt.21992","journal-title":"J. Graph Theory"},{"key":"22_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-319-08404-6_8","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"P Bonsma","year":"2014","unstructured":"Bonsma, P., Kami\u0144ski, M., Wrochna, M.: Reconfiguring independent sets in claw-free graphs. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 86\u201397. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-08404-6_8"},{"key":"22_CR7","unstructured":"Bousquet, N., Mouawad, A.E., Nishimura, N., Siebertz, S.: A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems. arXiv preprint arXiv:2204.10526 (2022)"},{"key":"22_CR8","doi-asserted-by":"publisher","unstructured":"Bria\u0144ski, M., Felsner, S., Hodor, J., Micek, P.: Reconfiguring independent sets on interval graphs. In: Bonchi, F., Puglisi, S.J. (eds.) Proceedings of MFCS 2021. LIPIcs, vol. 202, pp. 23:1\u201323:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2021.23","DOI":"10.4230\/LIPIcs.MFCS.2021.23"},{"issue":"2","key":"22_CR9","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/PL00007241","volume":"17","author":"M Chen","year":"2001","unstructured":"Chen, M., Chang, G.J.: Families of graphs closed under taking powers. Graphs Comb. 17(2), 207\u2013212 (2001). https:\/\/doi.org\/10.1007\/PL00007241","journal-title":"Graphs Comb."},{"key":"22_CR10","doi-asserted-by":"publisher","unstructured":"Demaine, E.D., et al.: Linear-time algorithm for sliding tokens on trees. Theor. Comput. Sci. 600, 132\u2013142 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.07.037","DOI":"10.1016\/j.tcs.2015.07.037"},{"key":"22_CR11","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory. GTM, vol. 173. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3"},{"issue":"1","key":"22_CR12","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/s10878-012-9594-4","volume":"27","author":"H Eto","year":"2013","unstructured":"Eto, H., Guo, F., Miyano, E.: Distance-$$d$$ independent set problems for bipartite and chordal graphs. J. Comb. Optim. 27(1), 88\u201399 (2013). https:\/\/doi.org\/10.1007\/s10878-012-9594-4","journal-title":"J. Comb. Optim."},{"key":"22_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-662-48971-0_21","volume-title":"Algorithms and Computation","author":"E Fox-Epstein","year":"2015","unstructured":"Fox-Epstein, E., Hoang, D.A., Otachi, Y., Uehara, R.: Sliding token on bipartite permutation graphs. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 237\u2013247. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48971-0_21"},{"key":"22_CR14","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Company (1979)"},{"issue":"1\u20132","key":"22_CR15","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","volume":"343","author":"RA Hearn","year":"2005","unstructured":"Hearn, R.A., Demaine, E.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":"22_CR16","unstructured":"Hoang, D.A.: On the complexity of distance-$$d$$ independent set reconfiguration. arXiv preprint arXiv:2208.07199 (2022)"},{"issue":"12\u201314","key":"22_CR17","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., et al.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2010.12.005","journal-title":"Theor. Comput. Sci."},{"key":"22_CR18","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. Theor. Comput. Sci. 439, 9\u201315 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.03.004","journal-title":"Theor. Comput. Sci."},{"key":"22_CR19","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.dam.2020.03.052","volume":"308","author":"I Katsikarelis","year":"2020","unstructured":"Katsikarelis, I., Lampis, M., Paschos, V.T.: Structurally parameterized $$d$$-scattered set. Discret. Appl. Math. 308, 168\u2013186 (2020). https:\/\/doi.org\/10.1016\/j.dam.2020.03.052","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"22_CR20","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1006\/jagm.1998.9999","volume":"29","author":"PE Kearney","year":"1998","unstructured":"Kearney, P.E., Corneil, D.G.: Tree powers. J. Algorithms 29(1), 111\u2013131 (1998). https:\/\/doi.org\/10.1006\/jagm.1998.9999","journal-title":"J. Algorithms"},{"key":"22_CR21","first-page":"47","volume":"95","author":"M Kong","year":"1993","unstructured":"Kong, M., Zhao, Y.: On computing maximum $$k$$-independent sets. Congr. Numer. 95, 47\u201347 (1993)","journal-title":"Congr. Numer."},{"key":"22_CR22","first-page":"65","volume":"143","author":"M Kong","year":"2000","unstructured":"Kong, M., Zhao, Y.: Computing $$k$$-independent sets for regular bipartite graphs. Congr. Numer. 143, 65\u201380 (2000)","journal-title":"Congr. Numer."},{"issue":"1","key":"22_CR23","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/S089548019120016X","volume":"8","author":"YL Lin","year":"1995","unstructured":"Lin, Y.L., Skiena, S.S.: Algorithms for square roots of graphs. SIAM J. Discret. Math. 8(1), 99\u2013118 (1995). https:\/\/doi.org\/10.1137\/S089548019120016X","journal-title":"SIAM J. Discret. Math."},{"key":"22_CR24","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Mouawad, A.E.: The complexity of independent set reconfiguration on bipartite graphs. ACM Trans. Algorithms 15(1), 7:1\u20137:19 (2019). https:\/\/doi.org\/10.1145\/3280825","DOI":"10.1145\/3280825"},{"key":"22_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1007\/978-3-319-21840-3_42","volume-title":"Algorithms and Data Structures","author":"D Lokshtanov","year":"2015","unstructured":"Lokshtanov, D., Mouawad, A.E., Panolan, F., Ramanujan, M.S., Saurabh, S.: Reconfiguration on sparse graphs. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 506\u2013517. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21840-3_42"},{"key":"22_CR26","doi-asserted-by":"publisher","unstructured":"Mynhardt, C., Nasserasr, S.: Reconfiguration of colourings and dominating sets in graphs. In: Chung, F., Graham, R., Hoffman, F., Mullin, R.C., Hogben, L., West, D.B. (eds.) 50 years of Combinatorics, Graph Theory, and Computing, pp. 171\u2013191. CRC Press, 1st edn. (2019). https:\/\/doi.org\/10.1201\/9780429280092-10","DOI":"10.1201\/9780429280092-10"},{"key":"22_CR27","doi-asserted-by":"publisher","unstructured":"Nishimura, N.: Introduction to reconfiguration. Algorithms 11(4), 52 (2018). https:\/\/doi.org\/10.3390\/a11040052","DOI":"10.3390\/a11040052"},{"key":"22_CR28","doi-asserted-by":"publisher","unstructured":"Siebertz, S.: Reconfiguration on nowhere dense graph classes. Electron. J. Comb. 25(3), P3.24 (2018). https:\/\/doi.org\/10.37236\/7458","DOI":"10.37236\/7458"},{"key":"22_CR29","doi-asserted-by":"publisher","unstructured":"van den Heuvel, J.: The complexity of change. In: Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., vol. 409, pp. 127\u2013160. Cambridge University Press (2013). https:\/\/doi.org\/10.1017\/CBO9781139506748.005","DOI":"10.1017\/CBO9781139506748.005"},{"key":"22_CR30","doi-asserted-by":"publisher","unstructured":"van der Zanden, T.C.: Parameterized complexity of graph constraint logic. In: Proceedings of IPEC 2015. LIPIcs, vol. 43, pp. 282\u2013293. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2015). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2015.282","DOI":"10.4230\/LIPIcs.IPEC.2015.282"},{"key":"22_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2017.11.003","volume":"93","author":"M Wrochna","year":"2018","unstructured":"Wrochna, M.: Reconfiguration in bounded bandwidth and treedepth. J. Comput. Syst. Sci. 93, 1\u201310 (2018). https:\/\/doi.org\/10.1016\/j.jcss.2017.11.003","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"22_CR32","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1587\/transinf.2018FCL0002","volume":"102","author":"K Yamanaka","year":"2019","unstructured":"Yamanaka, K., Kawaragi, S., Hirayama, T.: Exact exponential algorithm for distance-3 independent set problem. IEICE Trans. Inf. Syst. 102(3), 499\u2013501 (2019). https:\/\/doi.org\/10.1587\/transinf.2018FCL0002","journal-title":"IEICE Trans. Inf. Syst."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-27051-2_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,13]],"date-time":"2023-03-13T00:05:53Z","timestamp":1678665953000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-27051-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031270505","9783031270512"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-27051-2_22","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":"13 March 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hsinchu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","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":"22 March 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 March 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.walcom2023.conf.nycu.edu.tw\/","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":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"75","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":"30","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":"0","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":"40% - 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":"10","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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This proceeding includes 2 invited papers.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}