{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T06:34:43Z","timestamp":1774506883167,"version":"3.50.1"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030398804","type":"print"},{"value":"9783030398811","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-39881-1_12","type":"book-chapter","created":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T08:02:33Z","timestamp":1580112153000},"page":"133-145","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Reconfiguring k-path Vertex Covers"],"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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5212-0202","authenticated-orcid":false,"given":"Akira","family":"Suzuki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsuyoshi","family":"Yagita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,20]]},"reference":[{"issue":"1\u20134","key":"12_CR1","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s13119-011-0002-7","volume":"1","author":"HB Acharya","year":"2012","unstructured":"Acharya, H.B., Choi, T., Bazzi, R.A., Gouda, M.G.: The $$k$$-observer problem in computer networks. Networking Sci. 1(1\u20134), 15\u201322 (2012)","journal-title":"Networking Sci."},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1142\/9781848162778_0004","volume-title":"Computability in Context","author":"Giorgio Ausiello","year":"2011","unstructured":"Ausiello, G., Bonifaci, V., Escoffier, B.: Complexity and approximation in reoptimization. In: Computability in Context: Computation and Logic in the Real World, pp. 101\u2013129. World Scientific, Singapore (2011)"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Beck, M., Lam, K.Y., Ng, J.K.Y., Storandt, S., Zhu, C.J.: Concatenated $$k$$-path covers. In: Proceedings of ALENEX 2019, pp. 81\u201391 (2019)","DOI":"10.1137\/1.9781611975499.7"},{"key":"12_CR4","unstructured":"Belmonte, R., Kim, E.J., Lampis, M., Mitsou, V., Otachi, Y., Sikora, F.: Token sliding on split graphs. In: Niedermeier, R., Paul, C. (eds.) Proceedings of STACS 2019. LIPIcs, vol. 126, pp. 13:1\u201313:7 (2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"key":"12_CR5","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":"12_CR6","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 Theor. 83(2), 164\u2013195 (2016)","journal-title":"J. Graph Theor."},{"key":"12_CR7","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"},{"issue":"12","key":"12_CR8","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"B Bre\u0161ar","year":"2011","unstructured":"Bre\u0161ar, B., Kardo\u0161, F., Katreni\u010d, J., Semani\u0161in, G.: Minimum $$k$$-path vertex cover. Discrete Appl. Math. 159(12), 1189\u20131195 (2011)","journal-title":"Discrete Appl. Math."},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.dam.2014.05.042","volume":"177","author":"B Bre\u0161ar","year":"2014","unstructured":"Bre\u0161ar, B., Krivo\u0161-Bellu\u0161, R., Semani\u0161in, G., \u0160parl, P.: On the weighted k-path vertex cover problem. Discrete Appl. Math. 177, 14\u201318 (2014)","journal-title":"Discrete Appl. Math."},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.tcs.2015.07.037","volume":"600","author":"ED Demaine","year":"2015","unstructured":"Demaine, E.D., et al.: Linear-time algorithm for sliding tokens on trees. Theor. Comput. Sci. 600, 132\u2013142 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR11","volume-title":"Graph Theory, Graduate Texts in Mathematics","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2010)","edition":"4"},{"key":"12_CR12","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":"12_CR13","doi-asserted-by":"crossref","unstructured":"Funke, S., Nusser, A., Storandt, S.: On $$k$$-path covers and their applications. In: Proceedings VLDB Endowment, vol. 7, no. 10, pp. 893\u2013902 (2014)","DOI":"10.14778\/2732951.2732963"},{"key":"12_CR14","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1990)"},{"issue":"1\u20132","key":"12_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)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"van den Heuvel, J.: The complexity of change. In: Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 409, pp. 127\u2013160. Cambridge University Press, Cambridge (2013)","DOI":"10.1017\/CBO9781139506748.005"},{"issue":"12\u201314","key":"12_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)","journal-title":"Theor. Comput. Sci."},{"key":"12_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)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/978-3-030-26176-4_30","volume-title":"Computing and Combinatorics","author":"M Kumar","year":"2019","unstructured":"Kumar, M., Kumar, A., Pandu Rangan, C.: Reoptimization of path vertex cover problem. In: Du, D.-Z., Duan, Z., Tian, C. (eds.) COCOON 2019. LNCS, vol. 11653, pp. 363\u2013374. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26176-4_30"},{"issue":"1","key":"12_CR20","doi-asserted-by":"crossref","first-page":"7:1","DOI":"10.1145\/3280825","volume":"15","author":"D Lokshtanov","year":"2019","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)","journal-title":"ACM Trans. Algorithms"},{"key":"12_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-319-75172-6_21","volume-title":"WALCOM: Algorithms and Computation","author":"E Miyano","year":"2018","unstructured":"Miyano, E., Saitoh, T., Uehara, R., Yagita, T., van der Zanden, T.C.: Complexity of the maximum k-path vertex cover problem. In: Rahman, M.S., Sung, W.-K., Uehara, R. (eds.) WALCOM 2018. LNCS, vol. 10755, pp. 240\u2013251. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-75172-6_21"},{"issue":"4","key":"12_CR22","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). (article 52)","journal-title":"Algorithms"},{"key":"12_CR23","first-page":"723","volume":"347","author":"Y Ran","year":"2019","unstructured":"Ran, Y., Zhang, Z., Huang, X., Li, X., Du, D.Z.: Approximation algorithms for minimum weight connected 3-path vertex cover. Appl. Math. Comput. 347, 723\u2013733 (2019)","journal-title":"Appl. Math. Comput."},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.03.013","volume":"783","author":"D Tsur","year":"2019","unstructured":"Tsur, D.: Parameterized algorithm for 3-path vertex cover. Theor. Comput. Sci. 783, 1\u20138 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR25","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)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR26","unstructured":"Zandenvan der Zanden, T.C.: Parameterized complexity of graph constraint logic. In: Proceedings of IPEC 2015. LIPIcs, vol. 9076, pp. 282\u2013293 (2015)"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-39881-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,24]],"date-time":"2021-02-24T02:18:40Z","timestamp":1614133120000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-39881-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030398804","9783030398811"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-39881-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"20 February 2020","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 Workshop on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Singapore","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Singapore","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 March 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 April 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.comp.nus.edu.sg\/~walcom20\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}